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

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

 

이전 문제였던 2xn 타일링과 비슷해 보이지만 2x2 타일이 추가되었다.

 

우선 2x2 타일을 추가하지 않은 경우 타일을 채우는 방법의 수를 점화식으로 표현하면 다음과 같다. 2xn 타일을 채울 방법의수 DP 테이블 배열 DP[N]이 있는 경우

DP[N] = DP[N - 1] + DP[N - 2]

 

하지만 2x2 타일이 추가되었기 때문에 세가지 사항을 고려해야 된다.

 

1.  N - 1번째에서 2x1짜리 타일 한 개 붙이는 경우

 

2. N - 2번째에서 1x2짜리 타일 두 개 붙이는 경우

 

2. N - 2번째에서 2x2짜리 타일 한 개 붙이는 경우

 

그러므로 점화식은 DP[N] = DP[N-1] + 2 * DP[N-2]가 된다.

 

이는 DP[3]부터 적용되므로 그 밑의 값 DP[1], DP[2]는 미리 구해야 한다.

DP[1]은 2x1 타일로 한가지 방법으로만 배치 가능하므로 1이고 DP[2]는 1x2 타일로 한가지, 2x1 타일로 한가지, 그리고 2x2 타일로 한가지 방법으로 배치 가능하므로 총 3이다.

 

고로 2xn에서 타일을 깔 수 있는 방법의 수는 DP[N]이 된다.

 

코드는 다음과 같다.

#include <iostream>
using namespace std;

int main()
{
	int input;
	cin >> input;

	int* dp = new int[input + 1];
	dp[0] = 0;
	dp[1] = 1;
	dp[2] = 3;

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

	cout << dp[input] << endl;
	delete[] dp;
}