비대칭 타일링

문제 : https://algospot.com/judge/problem/read/ASYMTILING

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 그 후 각 줄에 사각형의 너비 n (1 <= n <= 100) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 비대칭 타일링 방법의 수를 1,000,000,007 로 나눈 나머지를 출력합니다.

코드 ( C ++ ) 종만북 참조

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

const int MAX = 100+1;

int cache[MAX];

const int MOD = 1000000007;

int tiling(int width)

{

if (width <= 1) return 1;

int& ret = cache[width];

if (ret != -1)

return ret;

return ret = (tiling(width - 1) + tiling(width - 2)) % MOD;

}

int atiling(int width)

{

if (width % 2 == 1)

return (tiling(width) - tiling(width / 2) + MOD) % MOD; // 홀수인 경우 가운데에 2*1타일이 세로로 하나 놓일때

int ret = tiling(width);

ret = (ret - tiling(width / 2) + MOD) % MOD; // 짝수인 경우 반이 정확이 나뉘어 질때

ret = (ret - tiling(width / 2 - 1) + MOD) % MOD; // 짝수인 경우 가운데에 2*1타일이 가로로 두개 놓이고 반이 나눠질때

return ret;

}

int main()

{

int C;

cin >> C;

while (C--)

{

memset(cache, -1, sizeof(cache));

int num;

cin >> num;

int result = atiling(num);

cout << result << endl;

}

}