[주의][다이나믹 프로그래밍] 2×n 타일링 2

문제 링크 : https://www.acmicpc.net/problem/11727

2×n 타일링 2 성공 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 10574 6218 5084 59.351% 문제 2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.   예제 입력 1  2 예제 출력 1  3 예제 입력 2  8 예제 출력 2  171 예제 입력 3  12 예제 출력 3  2731

[ 문제 풀이 ]

- D[n] = 2 x n 크기의 직사각형을 채우는 방법의 수라고 뒀을 때, 

- N = 1일 때, 방법은 1가지이다. (D[1] = 1)

- N = 2일 때, 방법은 2가지이다. (D[2] = 3)

- N = n일 때, 방법은 (D[n] = D[n-1] + 2*D[n-2]) <-- ※ 이 문제의 경우는 동시에 일어나는 경우 곱해줘야 한다!

따라서, D[n-2] = D[n-1] + 2 * D[n-2] 이다.

[ 최종 구현(C++) ]

#include <stdio.h>
#define MAX_NUMBER_SIZE 1002

int D[MAX_NUMBER_SIZE] = { 0 };

int main(void)
{
	int N;
	scanf("%d", &N);
	
	D[1] = 1; D[2] = 3;

	for (register int i = 3; i <= N; i++)
	{
		D[i] = (D[i - 1] + (2 * D[i - 2])) % 10007;
	}

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

	return 0;
}