BOJ 11726 [2xn 타일링]

BOJ 2x 타일링 : https://www.acmicpc.net/problem/11726

안녕하세요. 이번 문제는 백준 온라인 저지의 "2xn 타일링" 입니다.

(2 x 5 타일)

(2 x 4 타일)                                                                                                                       (2 x 3 타일)

위 그림처럼, 2 x 5 타일을 만드는 방법은, 

1.    2 x 4 타일에서 2 x 1 타일 하나를 붙이는 방법과,

2.   2 x 3 타일에서 1 x 2타일 두 개를 붙여서 만드는 방법 두가지 입니다.

즉, 두 경우 [i - 1] 과 [i - 2]의 경우의 수를 더해주면, 어렵지 않게 [i]를 구할 수 있습니다.

#include <iostream>
using namespace std;
int DP[1001];
int main() {
    int N;
    cin >> N;
    DP[0] = 1;
    DP[1] = 1;
    if(N > 1) {
        for(int i=2; i<=N; i++)
            DP[i] = (DP[i-1]+DP[i-2]) % 10007;
    }
    cout << DP[N];
    return 0;
}