C++ 2xn 타일링

DP문제는 항상 그랬듯이 손으로 적어가면서 풀어야 합니다

 

2xn 타일링 문제는 대충 요런 느낌으로 직접 그려가면서 풀면 되겠습니다.

 

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int dp[1001] = {0,};
    
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;

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