[백준/BOJ] 백준 2133번 : 타일 채우기

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

2133번: 타일 채우기

 

다이나믹 프로그래밍을 통해 너비가 width인 타일(3*width)을 채우기 위한 경우의 수를 구하는 방법으로 문제를 해결했다. 이때 맨 처음 너비가 2인 블록으로 채우는 경우부터 2씩 증가하여 맨 처음 너비가 width인 블록으로 채우는 경우를 계산하여 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> cache(35, -1);

int Solve(int width)
{
	//너비가 홀수일때는 채울 수 없음
	if (width % 2 == 1)
		return 0;

	//모든 블록을 다 채웠을때
	if (width == 0)
		return 1;

	//너비가 2일때는 방법이 3개
	if (width == 2)
		return 3;

	int& ret = cache[width];

	if (ret != -1)
		return ret;

	ret = 0;

	for (int i = 2; i <= width; i = i + 2)
	{
		//맨 처음을 너비 2짜리 블록으로 채울 경우
		if (i == 2)
		{
			ret += (3 * Solve(width - i));
			continue;
		}

		//맨 처음을 너비 i짜리 블록으로 채울 경우
		//너비 i짜리 블록의 유니크한 가짓수는 2가지
		//(너비 i짜리 블록의 유니크한 가짓수가 아닌 경우는 이전에 (i 이하 너비)에서 처리 된다)
		ret += (2 * Solve(width - i));
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	cout << Solve(n);

	return 0;
}