[2133] 타일 채우기

문제

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

입력

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

출력

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

입력 1

2

출력 1

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

1. 문제 설명

• 일단 N이 홀수일 경우는 블록이 꽉 차게 들어가지 않기 때문에 타일이 완성되지 않아 경우의 수는 0이다.

• 위 그림을 보면, 규칙성이 있다. 길이가 2씩 늘어날 때마다 전 블록 오른쪽에 3x2 의 블록이 추가된다. 또 길이가 4씩 늘어날 때마다 두개의 블록이 추가된다고 생각했다. 그래서 여기까지의 점화식을 세우면 dp[i] = dp[i-2] * 3 + dp[i-4] * 2 이지만..

하.지.만.

• 실제로 쭉 그려보다보면 3x6 부분 이후로 3x8, 3x10.. 진행할때마다 새로운 타일이 계속해서 만들어진다. (3x6 부분 초록색 형광펜으로 칠한 도형 참고)
  이 도형은 3x2와 3x4 타일의 조합으로는 만들 수 없는 새로운 3x6의 타일이다.
  그러므로 길이가 2씩 늘어날 때마다 저 두가지 타일의 경우가 계속 추가되는 것을 반영해 주어야 문제를 해결할 수 있다.

2. 소스 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;

	cin >> n;

	vector<int> dp(n + 10, 0);

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

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

	return 0;
}