백준 - 타일링 : 1793번

https://www.acmicpc.net/problem/1793

1793번: 타일링

 

타일링 문제는 아래그림과 같이, N=1이면 1가지, N=2이면 2가지, N=3이면 3가지, N=4이면 5가지 경우가 있다.

아래 그림에 점선으로 표시된 부분을 자세히 보면,

점화식은 D(n)은 N*2 타일은 2*1, 1*2타일로 채울수 있는 방법의 수로 정의 할 수 있으며,

D(n) = D(n-1) + D(n-2) 가된다.

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int i,n;
    unsigned long x[1008];
    scanf("%d", &n);
    x[1] = 1;
    x[2] = 2;
    for(i=3;i<=n;i++)
    {
        x[i]=x[i-1]+x[i-2];
        x[i] =x[i]%10007;
    }
    printf("%d",x[n]);
    return 0;
}