문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

풀이

일단 N이 홀수면 타일을 채울 수 없다. 그러면 짝수일 경우에만 가능.
가장 기본적인 형태로써 타일을 채우는 방법은 다음과 같다.

i번째 칸을 채운다 할 때 DP[i-2]칸을 채운 경우에 마지막 두칸을 채우는 경우 3가지를 곱한 것이 i칸을 채우는 총 경우의 수다.
DP[i] = DP[i-2] * DP[2]
하지만 한가지 더 경우가 있다.

저 사이공간을 채우는 경우가 있는데 어떻게 칸을 채우느냐?
문제에도 나와있다.


저 사이를 위 그림과 같이 채우는 경우이다. 이처럼 채우는 경우의 수는

DP[i-4]경우에 두가지 경우를 곱하면 된다.
DP[i] = DP[i-4] * 2
그럼 총 DP의 경우의 수는
DP[i] = DP[i - 2] * dp[2] + dp[i-4] * 2

미처 생각 못한 부분

위 경우의 수가 점화식인줄 알았는데 한가지 간과한 부분이 있다.

이런 경우의 수도 나올 수 있다. 어떻게 채우느냐면 4칸일때와 똑같다.

이렇게 채우는 것을 i칸 전체 다 채울 수 있다.
따라서 반복문을 만들어서 점화식을 세워야 한다.

for (int j = 4; j <= i; j+=2)
	DP[i] += DP[i - j] * 2;

코드

#include <iostream>

using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	int *DP = new int[n + 1];

	DP[0] = 1;
	DP[1] = 0;
	DP[2] = 3;
	for (int i = 3; i <= n; i++)
	{
		if (i % 2 == 1)
			DP[i] = 0;
		else
		{
			DP[i] = DP[i - 2] * DP[2];
			for (int j = 4; j <= i; j += 2)
				DP[i] += DP[i - j] * 2;
		}
			
	}
	cout << DP[n] << endl;
	delete[] DP;
	return (0);
}