[BOJ 11727] 2 x n 타일링 2

문제는 여기에서 확인할 수 있다.

---

전형적인 Dynamic Programming 문제이다.

D[i] = {2 x i 직사각형을 타일로 채우는 방법의 수}라 정의하자.

그럼 약간의 관찰에 의해 $D[i] = D[i-1] + 2D[i-2]$가 성립한다.

#include<iostream>
 
using namespace std;
 
int num;
long long int cache[1001];
 
int main() {
    cin >> num;
    cache[1] = 1;
    cache[2] = 3;
    for(int i = 3; i <= num; i++)
        cache[i] = (cache[i-1] + 2*cache[i-2])%10007;
    
    cout << cache[num]%10007;
    
    return 0;
}