[11727] 타일링 2

풀이

구해야할 것 : 2 X n 크기의 직사각형을 타일로 채우는 방법의 수

2 X n 크기는

1. 2 x (n-1) 크기의 사각형에 가장 오른쪽에 세로로 타일을 하나 놓는 것
2. 2 X (n-2) 크기의 사각형에 가장 오른쪽에 가로로 타일 두 개를 놓는 것
3. 2 X (n-2) 크기의 사각형에 가장 오른쪽에 세로로 타일 두 개를 놓는 것

이렇게 단 세 가지 방법으로만 만들 수 있다.

문제를 정의할 때 오른쪽에만 타일을 추가한다고 생각해야 한다.

코드

#include <iostream>

int dp[1000001];
int n;

int main(void) {
	scanf("%d", &n);
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + 2 * dp[i - 2];
		dp[i] %= 10007;
	}
	printf("%d\n", dp[n]);
	return 0;
}