POLY(폴리오미노)

(출처) https://algospot.com/judge/problem/read/POLY

어떤 방법으로 세야지 POLY를 잘 셀 수 있을까

해당 문제는 세고자 하는 POLY 도형이 세로 단조라는 요소를 갖는다는 점이 문제를 푸는 핵심이었다. 세로 단조라는 특성으로 인해 POLY 도형의 각 줄은 항상 일렬로 늘어진 정사각형들의 모임이 될 수 밖에 없다.

따라서 맨 위의 첫번째 줄에 정사각형이 1개가 놓여졌을 때, 2개가 놓여졌을 때, ..., N개가 모두 놓여졌을 때의 경우로 각각 나눈 뒤 후에 나눠진 각각의 경우를 전부 합쳐준다면 원하는 답을 구할 수 있다.

이렇게 경우를 나누어 부분문제로 바꿔버리면, 나누어진 부분문제 또한 완벽하게 동일한 방식으로 다시 한번 나눌 수 있게 되므로 재귀적 연결이 가능하게 된다.

주의해야 할 점은 전 줄에 놓은 정사각형의 개수가 앞으로 만들 POLY 도형의 개수에 영향을 끼친다는 것. 전 줄에 몇 개의 정사각형을 놓았는지에 따라서 현재 줄과 앞으로 계속해서 다음 줄에 놓을 정사격형들의 모임이 움직일 수 있는 범위가 달라지기 때문이다. (움직임에 따라서 다른 모양의 POLY 모형이 되기 때문에 움직일 수 있는 모든 경우의 수를 세주어야 한다)

따라서 위의 조건을 고려해서 밑과 같은 점화식을 만들 수 있다.

poly[n][before] = 전 줄에 놓여진 정사각형의 개수가 before 개 일때, n개의 정사각형으로 만들 수 있는 poly 도형의 개수

poly[n][before] = (before * poly[n-1][1]) + ((before + 1) * (poly[n-2][2])) + ((before + 2) * (poly[n-3][3])) + ... + ((before + n - 1) * poly[0][n])

 
이때 poly[0][before]은 기저사례로 1을 return 한다. (더이상 놓을 정사각형이 없기 때문에, 전 줄에 before개의 정사각형이 놓여진 그냥 POLY 도형 1개로 바라봄)

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

int MOD = 10000000;
int cache[101][101];

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

	ret = 0;
	for (int i = 1; i < n + 1; i++) {
		if (before >= 1) ret = (ret + (((i + before) - 1) * (poly(n - i, i) % MOD))) % MOD;
		else ret = (ret + poly(n - i, i)) % MOD;	
	}

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		int n;
		cin >> n;
		memset(cache,-1,sizeof(cache));
		int ret = poly(n, 0);

		cout << ret << "\n";
		
	}
	return 0;
}

기억하고 싶은 점

MOD 연산이 제대로 되지 않아서 한참을 헤맸는데 한번 당했으니까 또 당하지는 않겠지.