[BOJ 11726] 2xn 타일링

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

 

풀이 :

 

DP 문제 입니다.

1X2 타일과 2X1 타일로 2XN을 타일링 할 때 아래의 규칙대로 쌓으면 됩니다.

 

규칙 1) 1X2 타일을 2 X (i - 1) 타일링 한 것에 덧붙인다.

규칙 2) 2X1 타일을 2X2 타일로 만들어 2 X (i - 2) 타일링 한 것에 덧붙인다.

 

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