[BOJ 11727] 2xn 타일링 2

문제 출저 : https://www.acmicpc.net/problem/11727

 

풀이 :

 

DP문제 입니다.

1x2 타일, 2x1타일, 2x2타일을 이용해 타일링을 합니다

2x1타일은 2x2타일로 만들어서 사용해야 하므로 2x2와 같은 경우에 들어가도록 계산하되, 다른 경우로 여겨주시면 됩니다.

 

N=1일때 1

N=2일때 3

N>=3일때 N-1패턴에서 1x2타일을 붙이는 경우, N-2패턴에서 2x1타일 2개, 2x2타일 1개를 붙이는 경우를 더하면 됩니다.

 

#include<stdio.h>
 
int n, cache[1001];
 
int main()
{
    scanf("%d", &n);
    cache[1] = 1;
    cache[2] = 3;
    for (int i = 3; i <= n; i++)cache[i] = (((cache[i - 2] * 2) % 10007) + (cache[i - 1] % 10007)) % 10007;
    printf("%d", cache[n]);
}