[백준] 2133번: 타일 채우기 C++ 풀이

문제

문제 분류

다이나믹 프로그래밍(동적 프로그래밍)

📌 풀이 방법

먼저 N이 2로 나누어지지 않는 경우는 타일을 완벽하게 채울 수 없습니다.

N을 천천히 늘려가며 칸수를 채우는 방식을 계산해보겠습니다.

 

N=2, 방법 3가지는 아래와 같습니다.

위 3가지 외에는 방법이 없으므로 dp[2] = 3입니다.

 

N=4인 경우

dp[2]: 2칸을 채우는 경우(3)

dp[4] = dp[2] * dp[2] 로 나타낼 수 있습니다.

 

N=6인 경우

먼저, dp[4] * dp[2] 를 더합니다.

이는 4칸의 블럭을 채우는 방법 * 2칸의 블럭을 채우는 방법입니다.

 

이후, 2칸을 먼저 채운 후 4칸을 채우는 방식인데, 이때 4칸을 채울 경우를 dp[4]로 계산하지 않고 '2' 로 계산합니다.

이유는 dp[4]로 계산할 시 위에서 dp[4] * dp[2]의 경우와 중복되는 경우가 발생합니다.

이때, 2가지 경우는 4칸을 만들 수 있는 특수한 경우를 의미합니다.

4칸 채우는 특수한 경우

 

3. 6칸을 채우는 특수한 경우

6칸을 채우는 특수한 경우는 아래만 존재합니다.

6칸 채우는 특수한 경우

 

N=6일 때 아래와 같은 식을 세울 수 있습니다.

dp[6] = dp[4] * dp[2] + dp[2] * 2 + 2

이는 아래와 같이 정리할 수 있습니다.

dp[6] = dp[4] * 3 + dp[2] * 2 + 2 * dp[0] (이때, dp[0]은 1이다.)

출처: https://www.acmicpc.net/board/view/158352

정리해보면 위의 사진처럼 생각해볼 수 있습니다.

(사진에는 K로 나와있지만 글에서는 N으로 표기)

dp[N-2] 인 경우는 총 3가지.

dp[N-4]인 경우는 2가지.

...

dp[N - 2k] 인 경우 2가지.

 

즉, 점화식은 아래와 같이 정리할 수 있습니다.

dp[N] = dp[N-2] * 3 + dp[N-4] * 2 + ... + dp[0] * 2

 

 

정답 코드

#include <iostream>
using namespace std;

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

 

참고 사이트

https://blog.naver.com/ajy7424/222608567553