[c++] 백준 2133번 - 타일 채우기

 

#백준 2133번 URL

2133번: 타일 채우기

 

이번에는 3*N 크기의 벽을 2*1, 1*2 크기의 타일로 채우는 경우의 수를 구하는 문제이다. 마찬가지로 다이나믹 프로그래밍을 이용하여 문제를 해결해보자.

 

 

 

3*1

n=1일 경우, 타일을 채울 수 있는 경우의 수가 0이다. 즉, d[1] = 0.

 

3*2

n=2일 경우, 아래와 같이 3가지의 방법이 있다. 즉, d[2] = 3이다. 

3*2 정렬 방법

 

n=3일 경우는 3*1의 타일이 세개가 연달아 나타나는 모양이므로 d[3]=0이다.

 

n=4일 경우는 n=2일 경우에 3*2 타일을 배치하는 경우이므로 d[4] = 3*d[2]의 경우의 수가 있다고 할 수 있다.

또한, n=6일 경우 d[6] = 3*d[4]가 되는데 여기서 3*2 타일의 모양이 두가지가 나오므로 2를 곱해준다.

 

즉, d[n] = 3*d[n-2] + (2*d[n-4] + 2*d[n-6] + ... + 2*d[0])의 점화식을 구할 수 있다.

 

이를 c++ 코드로 구현해보면,

 

#include <iostream>

using namespace std;

int d[10001];

int block(int n) {
	if (n == 1) return 0;
	else if (n == 0) return 1;
	else if (n == 2) return 3;
	
	if (d[n] != 0) {
		return d[n];
	}
	int result = 3 * block(n-2);
	
	for (int i = 3; i <= n; i++) {
		if (i % 2 == 0) {
			result += 2 * block(n - i);
		}
	}
	return d[n] = result;
	
}

int main() {
	int num = 0;
	scanf("%d", &num);
	printf("%d", block(num));
	
}