[TILING2] 타일링

[TILING2] 타일링 : https://algospot.com/judge/problem/read/TILING2

< 소스코드 > 

tiling(n) : 2 x n 크기의 사각형을 2 x 1 의 타일로 채우는 경우의 수.

#include <stdio.h>
#define MOD 1000000007
 
int d[101];
 
int tiling2(int n)
{
    if(n == 0) return 1;
    if(n < 0) return 0;
    if(d[n]) return d[n];
    
    return d[n] = (tiling2(n-1) + tiling2(n-2)) % MOD;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
        printf("%d\n", tiling2(n));
    }   
    
    return 0;
}

>> 2 x 1 하나를 채우고 나면 2 x n-1 크기를 채우면 된다.

>> 1 x 2 두개를 = 이렇게 채우고 나면, 2 x n-2 크기를 채우면 된다.