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

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

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

[ 문제 풀이 ]

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

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

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

- N = n일 때, 방법은 (D[n] = D[n-1] + D[n-2])

※ 위와 같이, 중복된 경우를 Count하지 않도록 주의한다!

따라서, D[n] = D[n-1] + 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] = 2;

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

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

	return 0;
}