[알고리즘 문제해결전략] TILING2 - 타일

[생각의 흐름]

1. 타일을 채우는 방법은 2개이다. 1) 세로로 채우는 방법 2) 가로로 채우는 방법 -> 결국 4X4타일이 됨

2. 타일을 n번째 까지 채웠을 때 그 이후 n+1 타일 부터 채우는 경우의 수를 개싱할 수 있다.

 

#include <stdio.h>
#include <memory.h>

const int MOD = 1000000007;
const int MAX_TILE_SIZE = 111;
int N;
int cache[MAX_TILE_SIZE];

int sol(int n)
{
    if(n == N)
        return 1;
    if(n > N)
        return 0; 

    int &ret = cache[n];
    if(ret != -1)
        return ret;
    // 타일을 세로로 쓰는 경우 + 타일을 가로로 2개 쓰는 경우
    ret = (sol(n+1) % MOD) + (sol(n+2) % MOD);

    return ret % MOD;
}

int main(void)
{
    int C;
    scanf("%d", &C);
    
    while(C--)
    {
        int n;
        scanf("%d", &N);
        memset(cache, -1, sizeof(cache));
        printf("%d\n", sol(0));
    }
    return 0;
}