[종만북 문제] 폴리오미노 (문제 ID : POLY, 난이도 : 중)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 언뜻 불가능해 보이는 문제도, 문제의 조건을 잘 보면 부분 문제의 조합으로 분해해 볼 수 있다!

---

[종만북 문제] 폴리오미노 (문제 ID : POLY, 난이도 : 중)

휴.. 맨 처음에는 무슨 문제인가 싶었지만, 결국 풀어내서 성취감이 있는 문제였다.

책에 있는 접근법을 조금 가져와 보자면...

위의 성질을 이용해서 점화식을 세우면 된다. 왜 이렇게 되냐면, 한 줄에 있는 블럭들은 서로 떨어져 있으면 안되고 붙어 있어야 하는 성질 때문이다! 😉

점화식은 대략 아래처럼 생겼다.

 

나 같은 경우, 처음에는 아래처럼 for-loop 으로 풀었었다. (추후 보기 편하라고 변수 명을 first, second 로 바꿈)

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

/****************************************************************************************************/

int N; // 블록의 갯수

constexpr int MOD = 10000000;

// [블록의 총 갯수] [첫 행의 갯수]
int cache[101][101];

// blocks : 사용 가능한 남은 블록의 갯수
int calc(int blocks)
{
	// 기본 케이스 세팅
	for (int i = 1; i <= N; ++i)
		cache[i][i] = 1;

	// 블록의 총 갯수
	for (int n = 2; n <= blocks; ++n)
	{
		// 제일 윗 행의 갯수
		for (int first = 1; first < n; ++first)
		{
			// 다음 하위 블록의 첫 행의 갯수
			for (int second = 1; second <= n - first; ++second)
			{
				int add = cache[n - first][second] % MOD;
				int multiply = first + second - 1;
				cache[n][first] = (cache[n][first] + (add * multiply) % MOD) % MOD;
			}
		}
	}

	int sum = 0;
	for (int i = 1; i <= blocks; ++i)
		sum += cache[blocks][i];

	return sum;
}

void sol()
{
	//fill(&cache[0][0], &cache[100][0] + sizeof(cache) / sizeof(cache[0][0]), -1);
	fill_n(&cache[0][0], 101 * 101, 0);
	
	cout << calc(N) % MOD << endl;
}

void inputHandler()
{
	cin >> N;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

 

그런데 책에서는 좀 더 깔끔하게, 재귀로 풀고 있다. 참고로만 첨부하겠다 ㅋㅋ

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

/****************************************************************************************************/

int N; // 블록의 갯수

constexpr int MOD = 10000000;

// [블록의 총 갯수] [첫 행의 갯수]
int cache[101][101];

// n 개의 정사각형이면서, 맨 위의 가로줄에 first 개의
// 정사각형을 포함하는 폴리오미노의 수를 반환
int calc(int n, int first)
{
   // 기저 사례 : n == first
   if (n == first)
      return 1;

   // 메모이제이션
   int& ret = cache[n][first];
   if (ret != -1)
      return ret;
   ret = 0;

   for (int second = 1; second <= n - first; ++second)
   {
      int add = second + first - 1;
      add *= calc(n - first, second);
      add %= MOD;
      ret += add;
      ret %= MOD;
   }

   return ret;
}

void sol()
{
   fill_n(&cache[0][0], 101 * 101, -1);

   int sum = 0;
   for (int i = 1; i <= N; ++i)
      sum = (sum + calc(N, i)) % MOD;

   cout << sum << endl;
}

void inputHandler()
{
   cin >> N;
}

int main()
{
   int cases;
   cin >> cases;
   while (cases--)
   {
      inputHandler();

      sol();
   }

   return 0;
}