POLY

#include <iostream>

using namespace std;

const int MAX_N = 101;
const int MOD = 10000000;

int cache[MAX_N][MAX_N];

int n;

int getTotPoly(int n);
int poly(int n, int top);

int main()
{
	int caseNum = 0;
	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin >> n;

		// Initialize
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				cache[i][j] = -1;

		// Process
		cout << getTotPoly(n) << endl;
	}
}

int getTotPoly(int n)
{
	int ret = 0;

	for (int top = 1; top <= n; top++)
		ret = (ret + poly(n, top)) % MOD;
	
	return ret;
}

int poly(int n, int top)
{
	int& ret = cache[n][top];
	if (ret != -1) return ret;
	
	// Initialize !!
	ret = 0;

	if (n == top) return ret = 1;

	for (int i = 1; i <= n - top; i++)
		ret = (ret + poly(n - top, i) * (top + i - 1)) % MOD;

	return ret;
}

이번 문제는 

poly(n) => n 개의 사각형으로 만들 수 있는 세로 단조 폴리오미노의 수

라고 규정해서는 풀 수가 없었다.

두 폴리오미노가 만날 떄, 접점이 되는 사각형의 갯수가 몇개냐에 따라 만들어지는 폴리오미노의 수가 달라졌기 때문이다.

그래서

poly(n, top) => n 개의 사각형으로 만들 수 있는 세로 단조 폴리오미노들 중

    맨 위의 사각형의 갯수가 top 개인 폴리오미노의 수

라고 새로 규정하였다.

즉,

                 n - top

poly(n, top) = ∑  [ poly(n - top, i) * (top + i - 1) ]

                        i = 1

을 구현하면 된다.

구현 자체는 그리 어렵지 않았는데,

poly() 함수 내에서 ret 을 0 으로 초기화 시켜주지 않아서 15 분? 정도 시간이 소요되었다.

PolyInput.txt

PolyOutput.txt