백준 2133: 타일 채우기

문제 요약

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

문제 분류

• 다이나믹 프로그래밍
• 비트마스킹

문제 풀이

백준에서는 다이내믹 프로그래밍만으로 분류가 되어있지만, 나는 비트마스킹으로 풀어서 분류에 비트마스킹을 추가하였다.

현재 열에서 타일이 채워진 유무의 상태를 비트마스킹으로 표현하는 DP문제이다. 현재 열을 idx라고 라고 idx이전의 열이 모두 채워져 있다고 가정하면 총 5가지 경우가 나온다.

현재 열 idx를 기준으로,

1. 모든 행이 비어있을 때
2. 맨 위의 행만 채워져 있을 때
3. 맨 위의 행만 비어 있을 때
4. 맨 아래의 행만 채워져 있을 때
5. 맨 아래의 행만 비어 있을 때

이렇게 각 경우로 나누어서 빈 상태부터 모든 경우로 채워나가면 된다. 또한 각 경우는 비트마스킹으로 표현하면 된다. 나는 맨 아래 행을 첫 번째 비트, 중간 행을 두 번째 비트, 맨 위의 행을 새 번째 비트로 두어서 상태를 나타냈다. 가령 110(2)은 맨 위의 행과 가운데 행이 채워져있고, 맨 아래의 행이 비워져 있음을 나타낸다. 이렇게 각 경우로 나타내어 최대한 왼쪽열을 빈틈없이 채우고, 다음 열의 삐져나온 부분들을 새로운 상태로 재귀호출하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <memory.h>

using namespace std;

int dp[31][1 << 4];
int n;

int sol(int idx, int state) {
	if (idx > n) return 0;
	if (idx == n) {
		if (state == 0) return 1;
		return 0;
	}
	if (dp[idx][state] != -1) return dp[idx][state];
	int& res = dp[idx][state];
	res = 0;
	if (state == 0)			// 해당 열의 모든 행이 비어있을 때
		res = sol(idx + 2, 0) + sol(idx + 1, 4) + sol(idx + 1, 1);
	else if (state == 4)	// 해당 열에 맨 위만 채워져있을 때
		res = sol(idx + 1, 0) + sol(idx + 1, 3);
	else if (state == 3)	// 해당 열에 맨 위만 비어있을 때
		res = sol(idx + 1, 4);
	else if (state == 1)	// 해당 열에 맨 밑만 채워져있을 때
		res = sol(idx + 1, 0) + sol(idx + 1, 6);
	else if (state == 6)	// 해당 열에 맨 밑만 비어있을 때
		res = sol(idx + 1, 1);
	return res;
}

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

	memset(dp, -1, sizeof(dp));
	cout << sol(0, 0);
	return 0;
}