[c언어/c++] 비대칭 타일링 ASYMTILING 동적계획법

그림과 같이 2 * n 크기의 직사각형을 2 * 1 크기의 타일로 채우려고 합니다. 타일들은 서로 겹쳐서는 안 되고, 90도로 회전해서 쓸 수 있습니다. 단 이 타일링 방법은 좌우 대칭이어서는 안 됩니다. 위 그림은 2 * 5 크기의 직사각형을 채우는 비대칭 타일링 방법 6가지를 보여줍니다. 다음의 2가지는 좌우대칭이기 때문에 세지 않습니다.

n 이 주어질 때 가능한 비대칭 타일링 방법의 수를 계산하는 프로그램을 작성하세요. 방법의 수는 매우 클 수 있으므로, 1,000,000,007 로 나눈 나머지를 출력합니다.

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

#include<stdio.h>

#include<algorithm>

#include<memory.h>

#define MOD 1000000007

using namespace std;

int n;

int cache[100];

int tile(int);

int symm(int w);

int main(){

int c;

scanf(" %d",&c);

for(int loop = 0 ; loop < c ; loop++){

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

scanf(" %d",&n);

printf("%llu\n",symm(n));

}

return 0;

}

int tile(int index){

if(index == n) return 1;

if(index > n) return 0;

if(cache[index] != -1) return cache[index];

return cache[index] = (tile(index+1) + tile(index+2))%MOD;

}

int symm(int w){

if(w%2 == 0){

return ( tile(0) - tile(w/2 - 1) +MOD)%MOD;

}

else{

return ( tile(0) - tile(w/2) - tile(w/2 - 1) +MOD)%MOD;

}

}