백준[baekjoon] 11333

 

www.acmicpc.net/problem/11333

11333번: 4×n 타일링

기존의 2 x n 타일링 문제에서 파생된 문제여서 점화식 도출이 쉬울거라 예상하였지만

결론적으로 매우 복잡하였고 스택오버플로우에서 나올수있는 경우의수를 도움받아

식을 찾게되었고 바텀업으로 n의 최대범위까지 답을 채운후 TC만큼의 질의를 바로 응답하였다.

 

각 a, b, c, d, f 값을 0, 1, 2, 3, 4 로 치환하여 dp배열을 채웠다.

 

<코드>

#include<bits/stdc++.h>

using namespace std;

const int MAX_N = 1e4+4;
const int MOD = 1e9+7;
int dp[MAX_N][5];

int f(int idx, int x)
{
    return (idx < 0 ? 0 : dp[idx][x]);
}

int add(int dest, int src){
    return (dest+src)%MOD;
}

void init()
{
    dp[0][4] = 1;
    for(int i=1; i<MAX_N; i++){
        for(int j=0; j<5; j++){

            int& ret = dp[i][j];
            if(j == 0) {
                ret = f(i-2, 4);
                ret = add(ret, f(i-2, 1));
                ret = add(ret, f(i-2, 2));
            }

            else if(j == 1)
                ret = f(i-1, 0);
            
            else if(j == 2)
                ret = f(i-2, 3);

            else if(j == 3){
                ret = f(i-1, 4);
                ret = add(ret, f(i-1, 2));
            }

            else{
                ret = f(i-3, 4);
                ret = add(ret, f(i-1, 0));
                ret = add(ret, f(i-1, 0));
            }
        }
    }
}

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

    init();

    int TC;
    cin >> TC;

    while(TC--){
        int x;
        cin >> x;
        cout << dp[x][4] << '\n';
    }

    return 0;
}