[baekjoon 2133] 타일 채우기- DP(동적 프로그래밍) (C++)

www.acmicpc.net/problem/2133

2133번: 타일 채우기

일반적인 타일 문제라 생각했지만 추가적인 아이디어가 필요한 문제였다.

3 X N의 벽을 2X1, 1X2로 채워야 한다.

또한 벽의 높이가 3이기 때문에 직접 찾아보면 N이 홀수이면 채울 수가 없다.

 

그러면 N이 짝수일 때 고려를 해보면

 

N = 2 일 때 

이 세가지 케이스가 등장한다. 가로 두 칸을 차지하는 이 블록 3개는 우리가 기본 타일 채우기 문제를 풀듯이 계속 사용된다.

 

N = 4 일 때

이 세 가지 블록이 기존 타일을 채우던 것처럼 너비 2개씩 차지하면서 구성하는 경우의 수는 DP [2] * 3이다.

그러나 4가지 케이스일 때 너비 4개를 차지하는 도형이 새롭게 등장한다.

바로 이 두 개의 도형으로 한꺼번에 4칸을 채우는 케이스가 추가된다.

 

N = 6일 때를 생각해보면 이렇게 세 경우로 나눠볼 수 있다.

여기서 내가 참 많이 헷갈렸는데 DP 배열은 이 전의 최대 경우의 수를 계속해서 저장하고 있다고 생각해서(실제로 맞긴 하다.) 두 번째 case를 왜 생각해줘야 하나 많이 고민을 했다.

 

첫 번째 case는  N = 4 일 때 저장해둔 도형들 뒤에 2개짜리 기본 도형 3개의 조합이다. 이는 평소에 타일 문제 풀듯이 뒤에 붙이는 경우이다.

 

두 번째 case는 많이 헷갈렸던 것인데, 처음에 생각했던 것이 기본 도형 3개로 N = 2와 N = 4를 구성하면 첫 번째 case와 겹치는 게 있지 않을까?라는 생각이었고, 실제로 거의 모든 case가 겹친다.

하지만 따로 생각해줘야 하는 경우는 바로 N=4일 때 새로 생긴 special case 너비 4개짜리 도형 때문이다.

 

현재 case1에서 구한 케이스들은 기본 도형 조합으로 너비 6개를 채웠고 special case(N=4) + 뒤에 기본 도형 3개의 조합이다.

따라서 기본도형 3개(N=2)가 앞이고, 뒤에 special case(N=4)이 붙는 경우가 바로 case 2이다.

 

그래서 결국 2*3이 계산되고, new case(N=6) 2개가 새롭게 추가된다.

new case(N=6)

이런 식으로 계속해서 더해주면 된다.

 

N = 8일 때는

이렇게 case가 총 4개이며, 

case1은 dp[6] * 보통 블럭 3가지 => dp[6] * 3

case2는 dp[4] * special case(N=4) => dp[4] * 2

case3은 dp[2] * special case(N=6) => dp[2] * 2

case4는 매번 튀어나오는 special case 2개이다.

 

매번 dp배열을 그 전 단계를 이용해서 경우의 수를 계산해줘야 한다는 점이 일반 타일 문제와 차이점이다.

왜 case2를 또 생각해야 할까?라는 의문이 들었었다.

왜냐면 special case(N=4)를 이용해서 만들 수 있는 경우의 수는 모두 dp[6]에 저장되어 있을 텐데? 

라고 생각했지만 그렇게 만들어진 dp[6]의 배열의 경우의 수는 이제 case1에서 뒤에 일반 도형 3가지가 붙음으로써 더 이상 special case(N=4)로 끝나는 도형이 아니게 된다.

 

따라서 N=8일 때의 special case(N=4) 짜리로 끝나는 경우의 수는 새롭게 계산해줘야 한다.

마찬가지로 case3에서 special case(N=6)도 여기선 이렇게 끝나지만 N=10이 되면 N=8 + N=2의 조합으로 더 이상 마지막에 있지 않게 된다.

 

나는 여기 이해하는데 시간을 좀 썼다. 어려워..

 

점화식은 DP[I] = DP[i-2] * 3 + DP[i-4] * 2 .... DP[0] * 2; (뒤에 계속해서 추가된다.)

 

#include <iostream>
#include <algorithm>
using namespace std;

int dp[31], N;

int main() {
	cin >> N;
	if (N % 2) {
		cout << 0;
		return 0;
	}

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

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

참고로 dp[0] = 1로 초기화해주어야 두 번째 for문을 돌면서 마지막 dp[0] * 2가 매번 생성되는 new case(2가지)로 더해진다.