[백준 / BOJ / SILVER 3] 11726 번 : 2xn 타일링

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

11726번: 2×n 타일링

문제 접근법

• 점화식을 세워 접근 하면 된다.
• 2xn의 직사각형이 있을 때 마지막에 1x2 타일이 없다고 가정하면 그 직사각형은 가로길이 n-1까지의 경우의 수 라고 볼 수 있다.
• 같은 경우로 2x1 짜리 타일이 없으면 가로길이 n-2까지의 경우의 수 라고 볼 수 있다.
• DP[N](2xn 까지의 경우의 수) = DP[N-1] + DP[N-2]가 성립한다.

아래는 코드입니다.

#include <cstdio>
 
int check[1001];
 
int main()
{
    check[1] = 1;
    check[2] = 2;
 
    int a;
    scanf("%d", &a);
 
    for (int i = 3; i <= a; i++)
    {
        check[i] = (check[i - 1] + check[i - 2]) % 10007;
    }
 
    printf("%d\n", check[a]);
    return 0;
}