[C++] BOJ 11726 - 2xn 타일링

문제 : http://boj.kr/11726

티어 : 실버3

 

이 문제를 풀기 위해서는 다이나믹 프로그래밍(DP, Dynamic Programming)이라는 기법을 사용하여 문제를 풀어야 한다.

$N$이 $1, 2, 3, ...$일때, 가능한 경우의 수를 직접 구해보면 특정 규칙을 찾을 수 있다.

 

$A_{i}$를 $N=i$일때 가능한 경우의 수라고 하고,

$(X, Y)$에서 한 패턴안에 가능한 가로블럭의 개수를 $X$, 가능한 세로블럭의 개수를 $Y$라고 하자.

 

$N=1$일때, $(0, 1)$ 총 1개.

$N=2$일때, $(2, 0), (0, 2)$ 총 2개.

$N=3$일때, $(2, 1), (2, 1), (0, 3)$ 총 3개.

...를 해보면,

$A_{i} = A_{i-1} + A_{i-2}$라는 관계식을 얻어 낼 수 있다.

위 식은 피보나치 수열의 관계식과 같다.

 

따라서, $O(N)$만에 답을 얻어 낼 수 있다.

dp[1]=1;
dp[2]=2;
int N;
cin >> N;
for(int i=3; i<=N; i++) {
    dp[i] = (dp[i-1] + dp[i-2]) % 10007;
}
cout << dp[N] % 10007;