무지개 달팽이

Q. 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

입력.

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력.

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

n 값 별로 그림을 그려보았을 때, 블록의 마지막은 길이가 1이 남거나 2가 남는다는 것을 알 수 있다.

그리고 길이 2의 경우에는 2 X 1 블록과, 2 X 2 블록이 올 수 있으므로 다음과 같은 식을 구할 수 있다.

dp[n] = dp[n - 1] + dp[n - 2] * 2

여기서 n의 값이 커질 수록 배열에 들어가는 값도 상당히 증가할 수 있으니,

int형 범위를 넘지 않도록 배열에 값을 넣어줄 때 10,007로 나눈 나머지를 그 값으로 해주었다.

#include <stdio.h>

int main(void) {
	int i, n, dp[1001];

	scanf("%d", &n);

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 3;

	for (i = 3; i <= n; i++)
		dp[i] = (dp[i-1] + dp[i-2] * 2) % 10007;

	printf("%d\n", dp[n]);

	return 0;
}