2xN Tiling_2

11727.cpp

#include <iostream>

/*
https://www.acmicpc.net/problem/11726 와 다를 바 없는 문제.

이 문제는 큰 타일의 마지막 부분을 보고
하부의 작은 여러 문제로 나눌 수 있다.
따라서 DP로 풀 수 있음.

D[n] = 2xN 크기의 직사각형을 1x2, 2x1, 2x2로 채우는 방법의 수

ㅁㅁ|ㅁ 가로 길이가 3일 경우 1x2를 사용해서 마지막을 채우는 경우
ㅁㅁ|ㅁ

ㅁ|ㅁㅁ 가로 길이가 3일 경우 2x1을 사용해서 마지막을 채우는 경우
  |- -
ㅁ|ㅁㅁ (위가 2x1로 채워 질 경우 밑은 무조건 2x1이 들어가야 하므로 2x1은 사실상 2x2라고 봐도 됨)

D[n-1] = 2xN크기의 직사각형의 마지막을 1x2를 사용해서 채우는 경우의 수
D[n-2] = 2xN크기의 직사각형의 마지막을 2x1을 사용해서 채우는 경우의 수
D[n-2] = 2xN크기의 직사각형의 마지막을 2x2를 사용해서 채우는 경우의 수

따라서 하부 문제 D[n-1] && 2xD[n-2]을 계산하면 됨.

문제점: 2x0의 경우 어떻게 해야 하는가?

입력값은 1보다 크므로 0이 입력되었을 때 출력값은 고민 할 필요가 없다
하지만 n이 2일 경우 D[n-2]의 값을 생각해야 함.
n이 2일 경우는 두 가지 경우가 있음, 맨 뒤가 1x2인 경우 / 맨 뒤가 2x1인 경우 / 맨 뒤가 2x2일 경우.
따라서 D[2]는 3이 되는데, 2*D[0] + D[1] 가 3이 되어야 하므로 구현상의 편의로 D[0]를 1로 놓고 함.
(아무것도 없는 경우의 수도 경우의 수로 치자는 말, 공집합도 집합으로 치듯이.)

*/

int main()
{
	int t;
	int d[1001] = { 0, };
	scanf("%d", &t);
	d[0] = 1;
	d[1] = 1;

	for (int i = 2; i < t + 1; i++)
	{
		d[i] = d[i - 1] + 2*d[i - 2];
		d[i] %= 10007;
	}
	printf("%d", d[t]);
}