[POLY] 폴리오미노

• 분류: 동적계획법, 경우의 수
  
• 난이도: 중
• 입력: 테스트 케이스 C, 정사각형의 수 N
• 출력: 정사각형 N개로 만들 수 있는 세로 단조 폴리오미노의 경우의 수를 구하여라. (단, 10,000,000이 넘을 경우 나머지를 출력한다.)
• 소스

#include <iostream>
#define MOD 10000000
using namespace std;

int cache[101][101];
int poly(int, int);
int calcPoly(int);

int main(){
	int C;
	cin >> C;

	//cache 초기화
	for (int i = 0; i < 101; i++){
		for (int j = 0; j < 101; j++){
			cache[i][j] = -1;
		}
	}

	for (int i = 1; i <= C; i++){
		int N;
		cin >> N;
		cout << calcPoly(N) << endl;
	}

	return 0;
}

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

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

	return ret;
}

/*
	n = 만들어야하는 정사각형의 수
	first = 첫 줄에 있는 정사각형의 수
	second = 두번째 줄에 있는 정사각형의 수
	first + second - 1 = 새로 만든 첫 줄을 두번째 줄에 붙이는 경우의 수
*/
int poly(int n, int first){
	if (n == first) return 1;
	int& ret = cache[n][first];
	if (ret != -1) return ret;
	ret = 0;

	for (int second = n - first; second > 0; second--){
		int count = ((first + second - 1) * poly(n - first, second)) % MOD;
		ret = (ret + count) % MOD;
	}

	return ret;
}

• 소스 설명:

1. int calcPoly(int n): 정사각형 n개로 만들 수 있는 모든 세로 단조 폴리오미노의 수를 출력한다. poly 함수를 호출하여 첫번째 줄에 들어가 정사각형의 수 first 를 n과 함께 전달하여 경우의 수를 계산한다.
2. int poly(int n, int first): 기저 사례(종료할 시점)을 n과 first가 같아질 때 1를 출력한다. 모든 정사각형 n개를 이용하여 한 줄로 만들었을 경우를 의미한다. 동적계획법(DP)를 이용하여 이미 계산된 경우 ret를 반환한다. 계산되지 않은 경우, 재귀함수를 이용하여 n-first개로 만들 수 있는 폴리오미노를 다시 계산한다. 두번째 줄에 들어갈 정사각형의 수를 second로 인자를 넘긴다. (first + second - 1)은 첫 줄과 두번째 줄이 만날 때 사용될 수 있는 경우의 수를 의미한다.

• 참고 사이트: https://algospot.com/judge/problem/read/POLY