[백준 BOJ][DP] 2133 타일 채우기

링크

www.acmicpc.net/problem/2133

2133번: 타일 채우기

풀이

 

3XN 크기의 벽을 2X1, 1X2 크기의 타일로 채우는 경우의 수를 구하는 문제이다.

일단 힌트를 가지고 N이 작은 경우를 나열해보면 아래와 같다.

 

접근하기

 

DP[N]을 3XN의 타일을 채우는 경우의 수라고 두자.

 

3X1과 3X3은 2X1, 1X2 크기의 타일로 채울 수 있는 경우가 없다. 즉, 3XN에서 N이 홀수일 때는 경우의 수가 0이 된다는 것이다.

그럼 N이 짝수일 때를 생각해보면, 3X2 크기를 채울 수 있는 방법이 3개가 있다.
3X4를 채울 수 있는 방법은 3X2 크기를 채운 경우의 수에 남은 3X2를 채울 수 있는 경우의 수를 곱한, 즉 DP[n-2]*3 개가 있을 것이다.

하지만 힌트를 보면 알 수 있듯, N이 4, 6 늘어갈 때마다 새로운 타일 배치 모양이 2개씩 늘어나는 것을 알 수 있다.
따라서 3X4를 채울 수 있는 방법은 DP[n-2]*3 + DP[n-4]*2 개일 것이다.

이러한 규칙으로 쭉 나열한 식이 위 사진에 쓰여있다.

 

 

점화식 찾기

 

DP[0]은 배열 초기 세팅을 위해 1로 두자.

답을 구하기 위해서 저 식을 분리해보면, DP[n-2]*3과 DP[n-4]+DP[n-6]+DP[n-8] ... 에 2를 곱한 부분으로 나뉠 것이다. 앞부분은 그냥 구하면 되지만 뒤에 부분은 계속해서 식이 추가되기 때문에 이를 기억할 또 다른 배열 arr[n]을 추가하면 좋을 것 같다.

arr[n] = DP[n-4] + DP[n-6] + DP[n-8] ... 이다.

그럼 점화식은 다음과 같다.

DP[n] = DP[n-2]*3 + arr[n]*2   (arr[n] = DP[n-4] + DP[n-6] + DP[n-8] ... (n>=4))

이제 코드를 보자.

 

 

코드

//2133_타일 채우기
#include <cstdio>
using namespace std;

int n, DP[50], arr[50];

int main() {
	scanf("%d", &n);

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

	for (int i = 4; i <= 30; i += 2) {
		arr[i] = arr[i - 2] + DP[i - 4]; // arr[n] = DP[n-4] + DP[n-6] + DP[n-8] ...
		DP[i] = 3 * DP[i - 2] + 2 * arr[i];
	}
	
	printf("%d\n", DP[n]);

	return 0;
}