DP_백준_2*n타일링_11726

1. dp[n] : 2*n 크기의 직사각형을 채우는 방법의 수

2. dp[n] = dp[n-1] + dp[n-2]

3. 초기화 : dp[0] = 1, dp[1] =1;

핵심 : 끝을 기준 즉 N번째 타일이 들어올 때 어떻게 변하는지를 알아야 한다.

#include <iostream>
using namespace std;
 
int d[1005];
int dp(int num) {
    if (d[num] > 0) {
        return d[num];
    }
    d[num] = (dp(num - 1) + dp(num - 2)) % 10007;
    return d[num];
 
}
 
int main() {
    d[0] = 1;
    d[1] = 1;
    int n;
    cin >> n;
    cout << dp(n) << endl;
    return 0;
}