백준 11727 2×n 타일링 2(dynamic programming)

#include <iostream>
using namespace std;
 
int n;
int dp[1001];
void makeRectangle()
{
    dp[1] = 1;
    dp[2] = 3;
    for (int i = 3; i < 1001; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2]*2) % 10007;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    makeRectangle();
    cout << dp[n];
}

임의의 n의 값이 들어왔을 때 그릴 수 있는 경우의 수들 이다. 결국 n-1일 경우 다른 것이 없기 때문에 dp[n]을 구할 때 dp[n-1]을 그대로 더한다. 하지만, n-2일 경우 3가지의 경우로 나뉘게 된다. 그럼에도 불구하고 3배를 하지 않고 2배만을 하는 이유는 2x1 타일이 두 개 붙은 경우는 n-1인 경우에 포함되어 있기 때문이다.

따라서 구하고자하는 점화식은 dp[n]=dp[n-1]+dp[n-2]*2(i>=3) 이다.