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

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

11727번: 2×n 타일링 2

문제 접근법

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

아래는 코드입니다.

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