티스토리 뷰
https://algospot.com/judge/problem/read/TILING2
algospot.com :: TILING2
타일링 문제 정보 문제 2xn 크기의 사각형을 2x1 크기의 사각형으로 빈틈없이 채우는 경우의 수를 구하는 프로그램을 작성하세요. 예를 들어 n=5라고 하면 다음 그림과 같이 여덟 가지의 방법이 있
algospot.com
tiling(n) = 2*n 크기의 사각형을 타일로 덮는 방법을 반환한다
tiling(n) = tiling(n-1) + tiling(n-2)
#include <cstdio>
#include <cstring>
const int MOD=1000000007;
int cache[101];
int tiling(int n)
{
if(n<=1) return 1;
int &ret=cache[n];
if(ret!=-1) return ret;
return ret=(tiling(n-2)+tiling(n-1))%MOD;
}
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
memset(cache,-1,sizeof(cache));
printf("%d\n",tiling(n));
}
return 0;
}