백준 11333번 4*n 타일링

문제 링크입니다: https://www.acmicpc.net/problem/11333

규칙을 찾아서 재귀함수로 해결하고 싶었지만 역량이 부족했습니다.

결국 stackoverflow(https://stackoverflow.com/questions/22191801/given-an-integer-n-in-how-many-ways-can-we-tile-a-4-x-n-rectangle-with-3-x-1-ti)에서 점화식을 참고하여 풀 수 있었습니다.

*이런 문제는 규칙을 찾아서 점화식 세우는 것 밖에 답이 없는지 궁금합니다.

#include <iostream>

using namespace std;

 

const int MAX = 10000;

const long long MOD = 1000000007;

 

long long cache[MAX];

 

void preCalc(void)

{

        cache[0] = 1;

        cache[3] = 3;

        cache[6] = 13;

 

        for (int i = 9; i < MAX; i += 3)

                 cache[i] = (((5 * cache[i - 3]) % MOD) + MOD - ((3 * cache[i - 6]) % MOD) + cache[i - 9]) % MOD;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        int T;

        cin >> T;

 

        preCalc();

        for (int t = 0; t < T; t++)

        {

                 int N;

                 cin >> N;

 

                 if (N % 3)

                         cout << 0 << "\n";

                 else

                         cout << cache[N] << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~