11727 2 x n 타일링2

BOJ::11727 2xn 타일링2

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

2xn 크기의 직사각형을 채우는 경우

맨 마지막에 올 수 있는 경우는 3가지이다.

1.2x1 크기의 직사각형으로 끝나는 경우

2.1x2 크기 직사각형 두개로 끝나는 경우

3.2x2 크기 직사각형으로 끝나는 경우

1,2,3번 경우에 대해 각각 d[n-1], d[n-2], d[n-2] 이다.

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