<종만북> 08. 동적계획법_폴리오미노 (polyomino) c++

구하고자 하는 것은 세로 단조 폴리오미노이다. 세로 단조 폴리오미노가 되려면 각 가로줄에 포함된 정사각형은 항상 일렬로 연속해 있다.

첫 줄에 i개의 정사각형이 속한 폴리오미노의 개수는 나머지 n-i개로 구성된 정사각형들로 폴리오미노를 만든 뒤, 이들을 적절히 맨 윗 줄 아래에 붙여 주면 된다. 나머지는 정사각형들로 만들 수 있는 폴리오미노수는 재귀 호출로 구한다.

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

하지만 위의 그림을 보면 맨 윗줄과 나머지를 어떻게 붙이냐에 따라 다른 폴리오미노가 된다.

따라서 경우의 수를 정확히 계산하기 위해서는 나머지 사각형으로 만든 폴리오미노의 첫 번째 줄에 있는 정사각형의 수 별로 폴리오미노의 수를 반환 받을 수 있어야 한다.

poly(n, first)=n개의 정사각형을 포함하되, 첫 줄에 first개의 정사각형이 들어가는 폴리오미노의 수

첫 줄에 들어갈 정사각형의 수가 정해져 있으니 이제 n-first 개의 남은 정사각형들로 어떻게 폴리오미노를 만들지 생각해보자.

poly(n-first, 1) + poly (n-first, 2)+ ...+ poly(n-first, n-first)

예를 들어 맨 윗줄에 2개, 그 아랫줄에 3개의 정사각형이 있는 폴리오미노의 경우를 보자.

일반화하면 첫 줄에 first개의 정사각형이 있고, 나머지 사각형으로 만든 폴리오미노 첫 줄에 second개의 정 사각형이 있다고 할 때 이들을 붙일 수 있는 방법의 수는 first+second-1 이다.
이는 겹치는 부분이 반드시 1칸 존재해야 하기 때문이며, 사각형을 놓는 방법은 윗 행의 사각형 개수에 영향을 받는다는 것을 알 수 있다.

첫 째줄에 1개 둘 째줄에 사각형 1개를 놓았을 때부터 차근 차근 생각해본다.

#include<iostream>

using namespace std;
const int MOD = 10 * 1000 * 1000;
int cache[101][101];

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 = 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 sum = 0;
	memset(cache, -1, sizeof(cache));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
		sum+=poly(n, i);
	cout << sum << endl;

}

이거 솔직히 책 없었으면 1년동안 못 풀었다.. 사실 책 봐도 점화식을 이해하는데 상당한 시간이 걸렸다..