[Algospot] 폴리오미노 (문제 ID : POLY)

문제

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

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

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

 

입력

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

 

출력

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

---

어려운 문제였다. 정사각형을 어떻게 쌓을지, dp로 이걸 어떻게 해결할지 감이 잡히지 않았다. 결국 책을 보고 풀었다.

풀이 방법은 N개의 정사각형을 이용할 때 첫번째 줄에 first개의 정사각형을 쌓으면 몇개의 폴리오미노가 만들어지는지 함수와 dp배열을 통해 해결하는 것이었다. 첫째줄에 first개의 정사각형을 놓으면 그 다음줄엔 1개부터 N-first+1개 만큼의 정사각형이 올 수 있다. 이 때 첫째줄과 둘째줄에 가능한 조합수는 first + second -1개 이다. 이 조합수를 통해 첫째줄에 정사각형을 가운데에 놓는지 끝에 놓는지를 모두 커버할 수 있는 것이다. 결국 이런 완전탐색 방식을 통해 모든 조합수를 구할 수 있는 것이다.

poly(N,first)가 N개의 정사각형을 이용해 첫째줄에 first개의 정사각형을 놓는 방법의 수인데, 왜 poly(N,0)은 제대로 된 값을 반환하지 않는가가 의문이었다. 여러 input값을 넣으며 생각을 해보다가 함수 내에서 조합수에 따라 poly값에 곱해주는 부분이 잘못된 걸 발견했다. first가 0이라면 second가 1일땐 값을 더하지 않게 되는 문제가 있다. 따라서 조합수를 곱하는 부분을 삭제하고 poly(N,i)를 모두 하나씩 더하는 방식으로 고쳐서 해결했다. 왜 안되는지 좀 고민을 했는데 해결을 하니 뿌듯했다. 정답 판정도 제대로 받았다.

 

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/POLY.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
using namespace std;
int C, N;
int dp[101][101];
const int MOD = 10000000;
//n개의 정사각형 중 맨 위 가로줄에 first개의 정사각형을 갖는 폴리오미노 수 반환
int poly(int n, int first) 
{
	if (n == first) {
		return 1;
	}
	int& res = dp[n][first];
	if (res != -1) return res;
	res = 0;
	for (int second = 1; second <= n - first; second++) {
		if(first==0) res += (poly(n - first, second)) % MOD;
		else res += (poly(n - first, second) * (first + second - 1))%MOD;
		res %= MOD;
	}
	return res;
}


int main()
{
	cin >> C;
	while (C--) {
		memset(dp, -1, sizeof(dp));
		cin >> N;
		int sum = 0;
		/* 기존 코드에서 정답을 위한 방법
		for (int i = 1; i <= N; i++) {
			sum += poly(N, i);
			sum %= MOD;
		}
		cout << sum << endl; */
		//수정한 방법
		cout << poly(N, 0) << endl;
	}
}