[BOJ] 2718번: 타일 채우기

풀이

dp[i][j]를 i번째 칸, j의 상태에서 채울 수 있는 경우의 수로 놓고 풀어야 한다. 일차원 배열로 풀려고 하면 사실 경우의 수가 너무 많기 때문에 저렇게 2차원 배열을 이용하면 상대적으로 쉽게 풀 수 있다.

설명을 하기에는 너무 복잡하고 귀찮으므로 직접 찍은 영상을 통해 풀이를 하려고 한다.

코드

#include <cstdio>
int n, T, dp[10001][16];
const int div = 100007;
int main()
{
    dp[0][15] = 1;
    for (int i = 1; i <= 10000; ++i)
    {
        for (int j = 0; j <= 15; ++j)
        {
            dp[i][j] = dp[i - 1][15 - j];
        }
        dp[i][3] += dp[i - 1][15];
        dp[i][6] += dp[i - 1][15];
        dp[i][7] += (dp[i - 1][14] + dp[i - 1][11]);
        dp[i][11] += dp[i - 1][7];
        dp[i][12] += dp[i - 1][15];
        dp[i][13] += dp[i - 1][14];
        dp[i][14] += (dp[i - 1][7] + dp[i - 1][13]);
        dp[i][15] += (dp[i - 1][15] + dp[i - 1][3] + dp[i - 1][12] + dp[i - 1][6]);
    }
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        printf("%d\n", dp[n][15]);
    }
    return 0;
}