[백준 11726]2×n 타일링, DP

패턴을 찾고 점화식을 세우는 문제.
시간 복잡도 : O(N)
점화식 : An = An-1 + An-2

백준 Q11726

Sample Source Code

import java.util.Scanner;

public class Main {

	static int[] data = new int[1001];

	public static int dp(int x) {
		if(x == 1 ) return 1;
		if(x == 2 ) return 2; // n이 2일때 2가지 반환 Case 2가지
		if(data[x] != 0) return data[x];
		
		data[x] = dp(x-1) + dp(x-2);
		return data[x]%10007;
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.println(dp(sc.nextInt()));
		// 9 입력시 55 응답
	}
}