2xn 타일링 (백준 - 1149번)

동적계획법을 사용하는 문제이다.

 

2x1 크기부터 타일을 채울 수 있는 방법의 수를 그려보면 다음과 같은 결과가 나온다.

 

2x1 

=> 1개

 

2x2

=> 2개

 

2x3

=> 3개

 

2x4

=> 5개

.....

 

규칙을 보면 피보나치와 같다.

F[i] = F[i - 2] + F[i - 1] 

 

하지만 2x1000까지 방법의 수는 int로 표현할 수 없으며 10007를 나눈 나머지를 출력하라고 하였기 때문에 방법의 수를 10007로 나눈 값을 dp 테이블에 기록하면 된다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	int dp[1000 + 1];
	int input;
	cin >> input;

	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 2;

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