POLY 폴리오미노 :: 알고스팟

문제 : https://algospot.com/judge/problem/read/POLY

문제

정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.

예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아닙니다.

n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작성하세요.

코드 ( C++ ) 종만북 참조

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	const int MOD = 10 * 1000 * 1000;
	int cache[101][101];
	// n 개의 정사각형으로 이루어졌고, 맨 위 가로줄에 first개의
	// 정사각형을 포함하는 폴리오미노의 수를 반환한다.
	int poly(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 *= poly(n - first, second);
	add %= MOD;
	ret += add;
	ret %= MOD;
	}
	return ret;
	}
	int main()
	{
	int C;
	cin >> C;
	while (C--)
	{
	memset(cache, -1, sizeof(cache));
	int n;
	cin >> n;
	int ans = 0;
	for (int i = 1; i <= n; ++i)
	{
	ans += poly(n, i);
	ans %= MOD;
	}
	cout << ans << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub