문제

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

입력

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

출력

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

풀이

코드

#include <iostream>
using namespace std;

long long dp[1001];

int main()
{
	int n;
	scanf("%d", &n);

	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++)
	{
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[n] << endl;
	return 0;
}

처음엔 dp 배열에서 i가 홀수이면 i-1 배열에서 +1을 해주고, 짝수이면 i/2열에 * 2를 해준 후 +1을 해주면 되는줄 알았는데 틀렸다고 나왔다.
그래서 구글링해본 결과 dp[i-1] + dp[i-2]을 해주면 된다고 하는데...
처음엔 이해가 안갔다.
그림을 그려서 보니 이해가 됬는데

[i-1]일 때는 오른쪽 부분 마무리가 세로로 되는 것이고, [i-2]일 때는 오른쪽이 가로로 채워지며 마무리가 된다. 이렇게 자동적으로 마무리가 되기 때문에 [i-1] + [i-2]라는 점화식이 세워진다.