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

https://www.acmicpc.net/problem/2133

 

dp로 해결할 수 있는 문제

 

n = 1일때는 0이다.

 

n = 2 일때는 3이다. 아래 그림을 숫자로 표현하자면 (12, 34, 56), (13, 24, 56), (12, 35, 46)이다.

1	2
3	4
5	6

 

n = 3 일때는 0이다. 왜냐면 기본 블럭은 2개씩인데 n이 홀수 일때는 다 채울 수 없고 하나가 남기 때문이다.

1	2	3
4	5	6
7	8	9

 

따라서 n = 짝수 일때의 경우의 수를 구해보면 되는데 4일때도 한번 보자

1	2	3	4
5	6	7	8
9	10	11	12

 

경우의 수가 생각보다 많다. 어떻게 계산해야할까

 

n = 2 일때 경우의 수가 하나더 옆에 있으니까 단순하게 3 * 3을 해서 구할 수 있을것같지만 23블럭이 하나로 합치는 경우도 생각해야한다. 그렇다면 1 x 2블록이 두개가 가운데에서 만났을때 2*1블로 두개로 대체할 수 있으니까. 3 * 3 + 2일 수도 있겠다. 우선 3 x 2 네모를 기본으로 하고 나머지를 계산해야한다.

 

dp를 이용한다면 dp[i]가 경우의 수이고 식을 세우자.

 

#include <iostream>
#include <algorithm>
#define MAX 31
using namespace std;
int dp[MAX] = { 0, };
int main(int argc, char* argv[])
{
	int n;
	cin >> n;
 
	if (n % 2 == 1) {
		cout << 0 << '\n';
		return 0;
	}
 
	dp[0] = 1;
	dp[1] = 0;
	dp[2] = 3;
	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[i] + (dp[j] * 2);
		}
	}
 
	cout << dp[n] << '\n';
 
	return 0;
}