[백준] 2 x n 타일링

문제 링크

 

풀이

동적 계획법은 d[n]을 정의하고 그에 맞는 점화식을 세우는 것이 중요합니다. 점화식은 수열에서 이웃하는 두 개의 항 사이의 관계를 나타는 관계식입니다. 조금 더 쉽게 말하면 n번째 항의 값을 구하려면 n-1번째 항의 값을 알아야 합니다. n-1번째 항의 값을 알려면 n-2항의 값을 알아야 합니다. 이렇게 가다 보면 첫 번째 항을 알고 있다면 두 번째 항의 값을, 세 번째 항의 값을 알 수 있습니다. 때문에 초기값을 정의하고 항 사이의 관계식을 만들면 점화식이 완성됩니다.

 

출처
https://ko.wikipedia.org/wiki/%EC%A0%90%ED%99%94%EC%8B%9D

https://blog.naver.com/ao9364/221651296608?viewType=pc

 

이 문제에서 d[n]은 2 x n 타일을 채우는 방법의 수입니다. d[1]은 1이고 d[2]은 2입니다. 일단 최소한의 초기값은 정해진 것 같습니다. 항 사이의 규칙을 찾아야 하는데요. 다음 그림을 봅시다.

마지막(혹은 처음) 모양을 두 가지로 고정할 수 있습니다. 때문에 d[n] = d[n-1] + d[n-2] 이라는 식을 만들 수 있습니다.  d[3]은 3이고 그림은 다음과 같습니다.

코드

#include <cstdio>
int main()
{
	int n;
	scanf("%d", &n);
	int d[1001] = {};
	if (1 == n || 2 == n)
		printf("%d\n", n);
	else
	{
		d[1] = 1;
		d[2] = 2;
		for (int i = 3; i <= n; ++i)
			d[i] = (d[i - 1] + d[i - 2]) % 10007;
		printf("%d\n", d[n]);
	}	
}