문제

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

정사각형들의 변들을 서로 완전하게 붙여 만든 도형들을 폴리오미노(Polyomino)라고 부릅니다. n개의 정사각형으로 구성된 폴리오미노들을 만들려고하는데, 이 중 세로로 단조(monotone)인 폴리오미노의 수가 몇 개나 되는지 세고 싶습니다. 세로로 단조라는 말은 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는다는 뜻입니다.

예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노입니다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아닙니다. (c)는 맨 오른쪽 아래 있는 정사각형이 다른 정사각형과 변을 완전히 맞대고 있지 않기 때문에 폴리오미노가 아닙니다.

n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1≤C≤50)가 주어집니다. 그 후 각 줄에 폴리오미노를 구성할 정사각형의 수 n (1≤n≤100)이 주어집니다.

출력

각 테스트 케이스마다, n개의 정사각형으로 구성된 세로 단조 폴리오미노의 수를 출력합니다. 폴리오미노의 수가 10,000,000 이상일 경우 10,000,000으로 나눈 나머지를 출력합니다.

풀이(책 참고)

도형 문제를 풀기 위해서 이를 수치적으로 해석해야 하는데, 그런 부분이 쉽지 않았다. 특히, 어느 부분에서 메모이제이션을 적용시켜야 할지 전혀 감이 잡히지 않아 책을 참고하게 되었다.

힌트는 정사각형을 교차하지 않도록 배치해야 한다는 것이다. 이 조건 때문에 세로기준으로 볼 때 한 줄에 사각형을 쭉 이어서 배치하면 된다. 따라서, 각 줄에 배치되어야 할 사각형의 개수를 고려하여야 하므로, 다음과 같은 메서드를 생각할 수 있다.

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

그런데, 각 줄에 정사각형의 개수가 정해졌다고 해서 경우의 수가 계산되는 것이 아니라, 각 줄을 이어 사각형을 완성시킬 때 사각형이 이어붙어야 하므로(분리되면 안되므로) 이러한 경우까지 고려하여야 한다. 따라서 메서드는 다음과 같이 고려한다.

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

이 때, 첫번째 줄에 first개의 정사각형이 들어가면 나머지 줄에는 n-first개의 정사각형들이 배치되어야 한다. 두 번째 줄에 배치되는 정사각형의 수가 second개라 할 때, 첫 번째 줄과 두 번째 줄을 연결하는 경우의 수는(first+second-1)개가 생기므로, 이 경우를 각각의 경우에 곱하여야 한다. 따라서 메서드는 다음과 같이 정의할 수 있다.

static 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;
		}
		cache[n][first] = ret;
		return ret;
		
	}

세로 단조 폴리오미노를 만드는데 필요한 개수와, 첫번째 줄에 들어가는 정사각형의 수를 통해 메모이제이션을 적용하였다. 핵심은, 첫번째 줄에 들어가는 정사각형의 수를 고려하여 주어진 문제의 조건에 부합하도록 메소드를 정의한 것이다.