[백준] 타일 채우기 (2133번)

문제

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

입력

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

출력

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

---

타일 채우기의 응용문제이다.

일단 3*2의 크기를 채우는 방법은 3개라는 걸 알고 있다.

그리고 타일의 길이는 짝수여야만 채울 수 있다.

 

당장 점화식을 세워보면 일단 dp[N] = sum( dp[N-2]*dp[2], dp[N-4]*dp[4], dp[N-6]*dp[6] ... )이 떠오른다.

길이 N을 2의 배수로 각각 나눌 수 있기 때문이다.

이 문제에서 함정은 N이 2가 늘어날 때 마다 특수한 경우 2가지가 추가된다는 것이다.

가로 타일이 가운데에 쭉 깔리는 경우인데 이 2가지 경우를 추가해주면 된다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/BaekJoon/2020/%ED%83%80%EC%9D%BC%20%EC%B1%84%EC%9A%B0%EA%B8%B0%20(2133%EB%B2%88).cpp

chosh95/STUDY

C++ 코드

#include <iostream>
using namespace std;
int N;
int dp[301];

int main()
{
	cin >> N;
	dp[2] = 3;
	for (int i = 4; i <= N; i += 2) {
		dp[i] = dp[i - 2] * dp[2];
		for (int j = 4; j <= i - 2; j += 2) {
			dp[i] += dp[i - j] * 2;
		}
		dp[i] += 2;
	}
	cout << dp[N];
}