[BOJ] 2133번: 타일 채우기

2133번: 타일 채우기

풀이

f(2)를 계산하고 바로 D[n]=3∗D[n−2]D[n] = 3 * D[n - 2]D[n]=3∗D[n−2]라고 생각할 수 있지만
2(D[n−4]+D[n−6]+D[n−8]+...)2(D[n - 4] + D[n - 6] + D[n - 8] + ... )2(D[n−4]+D[n−6]+D[n−8]+...)0이상까지 추가로 더해야 줘야 한다.

그 이유는 힌트 속 그림에 있다.

코드

#include <cstdio>

int n, dp[10001] = {1, 0, 3};

int main()
{
    scanf("%d", &n);
    for (int i = 4; i <= n; ++i)
    {
        dp[i] = 3 * dp[i - 2];
        for (int j = 4; j <= i; j += 2)
        {
            dp[i] += 2 * dp[i - j];
        }
    }
    printf("%d\n", dp[n]);
    return 0;
}