[C++] 2×n 타일링 2 (백준 11727번)

https://www.acmicpc.net/problem/11727

 

#include <iostream>
#include <vector>
using namespace std;

int mod = 10007;

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

    int n;
    cin >> n;
    vector<int> dp(n + 1, 0);

    dp[1] = 1;
    if (n > 1) dp[2] = 3;
    for (int i = 3; i <= n; i++) {
        dp[i] = (2 * dp[i - 2] + dp[i - 1]) % mod;
    }

    cout << dp[n] << '\n';
}

점화식: dp[n] = (2 * dp[n - 2] + dp[n - 1]) % mod

(n - 2)까지 채운 것에 1 * 2 타일 2개 또는 2 * 2 타일 1개 붙이기 + (n - 1)까지 채운 것에 1 * 2 타일 1개 붙이기

처음에는 dp[n] = (3 * dp[n - 2] + dp[n - 1]) % mod로 잘못 생각했다. 중복되는 경우가 있기 때문에 (n - 2)까지 채운 것에서 붙이는 것과 (n - 1)까지 채운 것에서 붙이는 것을 따로 생각해주어야 한다. (AC)