알고스팟: 폴리오미노 (ID: POLY)

[문제 링크]

algospot.com :: POLY

---

최상단에 블록을 몇개 놓느냐에 따라 그 아래 블록에 놓을 수 있는 경우의 수가 정해진다.

 

n개의 블록으로 폴리오미노를 만든다고 했을 때, 최상단에 블록 2개를 놓는다면 그 아래 블록은 n-2개의 블록으로 폴리오미노를 만드는 경우와 같다.

또한 최상단 블록과 그 아래 블록을 한칸씩 엇갈리게(?) 놓는 경우도 있으므로 이 경우만큼 곱해주어야 한다.

최상단 블록을 first, 그 아래 블록을 second라고 했을 때, 엇갈리게 놓는 경우의 수는 (first + second - 1) 이다.

 

따라서 이 문제는 큰 문제를 작은 문제로 쪼갤 수 있기 때문에 재귀호출로 구현할 수 있으며

블록의 개수를 n, 최상단에 놓는 블록의 개수를 first 로 하여 2차원 배열에 메모라이징을 적용할 수 있다.

---

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

const int MOD = 10000000;
int memo[101][101];		

int Solution(int n, int first)
{
	if (n == first) return 1;

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

	ret = 0;
	for (int second = 1; second <= n - first; second++)
	{
		int add = first + second - 1;
		add *= Solution(n - first, second);
		add %= MOD;
		ret += add;
		ret %= MOD;
	}
	return ret;
}
int main(void)
{
	memset(memo, -1, sizeof(memo));
	int tc;
	cin >> tc;
	while (tc--)
	{
		int n;
		cin >> n;
		int ret = 0;
		for (int i = 1; i <= n; i++)
		{
			ret += Solution(n, i);
			ret %= MOD;
		}
		cout << ret << endl;
	}

	return 0;
}

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