[C++] 백준 11726 2xn 타일링 DP

풀이

1. 전체 타일은 가로축으로만 늘어난다. 

2. 전체 타일이 2x3 일때 가능한 경우는 =, ll 이다.

3. 전체 타일이 2x3 일때 가능한 경우는 =l, l=, lll 이다.

4. 타일을 붙이는 경우는 l 또는 = 인데, 타일이 하나 늘어날 경우 l을 붙이거나 하나 줄인 상태에서 =를 붙이는 경우가 가능하다. -> l를 붙이는 것은 n-1의 모든 경우의 수에 대해 가능하다. 또한 =를 붙이는 것도 n-2 모든 경우의 수에 가능하다.

5. 따라서 n에서 가능한 경우는 n-2 경우의 수와 n-1 경우의 수의 합이다. (dp[n] = dp[n-2] + dp[n-1])

리뷰

nx2를 nxn으로 착각해서 점화식을 어떻게 세우나 한참 고민했다. 문제를 잘 읽자.

#include <iostream>
#include <vector> 
#include <cstring>

using namespace std; 

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

    freopen("11726.txt", "r", stdin);

    int num;

    cin >> num;
    int dp[num+1];
    memset(dp, 0, sizeof(dp));
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= num; i++) {
        dp[i] = (dp[i-1] + dp[i-2])%10007;
    }
    
    cout << dp[num] << endl;
    return 0;
}