엄청 어려운 2133 타일 채우기

www.acmicpc.net/problem/2133

 

dp[n] = 3xn 직사각형 채우는 방법의 수

 

1. n이 홀수면 채울 수 없다

2. n=2면

3가지 방법이 있다

 

3. n=4면

3x2만큼은 dp[2]에서 했던 값을 사용, 나머지 3x2에 대한 방법이 또 3가지 있다

dp[2]에서 했던 부분을 왼쪽을 잡든 오른쪽을 잡든 같으니까 같은 수로 친다

dp[2]x3=9만큼의 경우의 수가 나온다

 

그리고 특수 케이스가 있다

이렇게 엇갈리는 방법 두 가지가 있다

 

dp[4]=dp[2]*3+dp[0]*2 가 된다. dp[4]=11

 

3. n=6이면

dp[2]+dp[4]

이렇게 볼 수 있지만 둘은 중복되는 모양이 너무 많다

그래서 일단 dp[2]*dp[4]를 해 놓고, 중복 없이 나머지를 넣어야 한다

dp[2]*dp[4]로 포함하지 못 하는 모양은 dp[4]에서 나온 특수한 경우+dp[2]가 반대쪽에 있는 경우이다

그걸 따로 더한다

 

 

그리고 dp[6]에서도 특수한 경우가 2개 나온다

다 더해주면 dp[6]=41

 

4. n=8이면

그림 없이 생각한다

1) 3x6+3x2로 나누기

2) 3x2+3x6으로 나누기

3) 3x4+3x4으로 나누기

4) 특별한 경우

 

1)은 dp[6]*dp[2]로 구할 수 있다. 41*3=123

2) 1)에서 중복되지 않은 것만 포함해야 한다. 즉,  dp[6]에서 나온 특별한 경우 두 가지(3x6)가 반대쪽에 붙은 경우를 말한다. 3x8에 3x6을 채우고 남은 2칸을 채우는 경우의 수는 dp[2]가 가지고 있다. dp[2]*2=6

3)는 1)과 2)에서 중복되지 않은 것만 포함해야 한다. 지금 남은 건 dp[4]일 때의 특수 경우 2가지가 있다. dp[4]의 특수 경우(3x4)를 먼저 채운 뒤, 남은 3x4를 채워줄 경우의 수는 dp[4]이다. dp[4]*2=22

4) 3x8의 특수 경우가 또 있다. dp[0]*2=2

 

dp[8] = 123+6+22+2=153

 

 

 

점화식은 어떻게 되는 걸까

dp[8]을 기준으로 생각한다

dp[8]=(dp[6]*dp[2]) + (dp[4]*2)+(dp[2]*2)+(dp[0]*2)

 

마지막 특수한 경우를 '이전의 블록을 사용하지 않음'이라는 의미로 dp[0]으로 놓으면 규칙성이 보이는 식이 나온다

dp[n]=(dp[n-2]*dp[2]) + (dp[n-4]*2)+(dp[n-6]*2)+(dp[n-8]*2)+...+(dp[0]*2)

 

이것이 이 문제의 점화식이다

 

#include <iostream>
#include <algorithm>
using namespace std;
int dp[31]; //3xn 직사각형 채우는 방법의 수

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