백준 2133번: 타일 채우기

[문제 링크]

2133번: 타일 채우기

---

난이도 있는 타일채우기 문제였던거 같다.

 

점화식을 이해한다면 쉬운 문제지만 이해하기까지가 조금 까다롭다.

3XN 타일을 2칸짜리 블록(2X1, 1X2)으로 채워야하기 때문에 N이 홀수이면 채울 수 있는 경우의 수는 0이다.

 

또한 그림으로 3X4, 3X6 타일을 직접 그려보면 N이 2 증가할 때마다 새로운 모양으로 채우는 경우가 2개 생긴다.

따라서 점화식은 dp(N) = dp(N-2) * dp(2) + sum(dp(N-4 ~ N-(N-2)) * 2) + 2 로 나타낼 수 있다.

위 점화식을 구현하면 원하는 결과를 얻을 수 있다.

---

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

int memo[31];

int Topdown(int N)
{
	if (N % 2 == 1) return 0;
	if (N == 0) return 0;
	if (N == 2) return 3;
	

	int& ret = memo[N];
	if (ret != -1) return ret;

	ret = Topdown(N - 2) * 3;
	N -= 2;

	while (N > 0)
	{
		ret += Topdown(N - 2) * 2;
		N -= 2;
	}

	return ret += 2;
}

int Bottomup(int N)
{
	memo[0] = 1;

	for (int i = 2; i <= N; i += 2)
	{
		memo[i] = memo[i - 2] * 3;

		for (int j = 4; j <= i; j += 2)
			memo[i] += memo[i - j] * 2;
	}

	return memo[N];
}

int main(void)
{
	int N;
	cin >> N;

	memset(memo, -1, sizeof(memo));
	cout << Topdown(N) << endl;

	memset(memo, 0, sizeof(memo));
	cout << Bottomup(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 83 day