폴리오미노

문제

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

예를 들어 그림 (a)는 정상적인 세로 단조 폴리오미노이다. 그러나 (b)는 점선이 폴리오미노를 두 번 교차하기 때문에 세로 단조 폴리오미노가 아니다. (c)는 정상적인 폴리오미노가 아니다. n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 세는 프로그램을 작성하세요. 폴리오미노 수가 10,000,000 이상일 경우 10,000,000으로 나눈 나머지를 출력한다.

입력

첫 줄에는 테스트 케이스의 수 C(1~50)이 주어진다.

각 줄에 폴리오미노를 구성할 정사각형의 수 n(1~100)이 주어진다.

예제 입력 및 출력

입력

3

2

4

92

 

출력

2

19

4841817

소스 코드

#include <iostream>
using namespace std;

int Case;
int cache[101][101]; //cache[number][first]
const int mod = 10000000;

class Polyomino {
private:
	int number; //사각형 개수
public:
	void Input() {
		cin >> number;
	}
	int getNum() {
		return number;
	}
	int countPoly(int number, int first) {

		//이미 계산된 값 반환
		if (cache[number][first] != 0)
			return cache[number][first];

		//가로로 한줄인 경우 캐시에 1저장 후 반환 -> 1개밖에 만들 수 없음
		if (number == first) {
			cache[number][first] = 1;
			return cache[number][first];
		}
		
		// 경우의 수 검사
		// number개의 정사각형, 첫줄에 first개 사용 
		// 두번째 줄에는 1개~number-first개 만큼 사각형이 올 수 있다
		for (int second = 1; second <= number - first; second++) {
			// 두번째 줄에 몇개의 사각형이 올지 결정하면 그 사각형은 second+first-1만큼 이동할 수 있다.
			// 처음 1개 곂치는 경우~마지막 1개 곂치는 경우까지 모두 second+first-1이다.
			for (int i = 0; i < second + first - 1; i++) {
				cache[number][first] += countPoly(number - first, second); //재귀함수 호출
				cache[number][first] %= mod;
			}
		}
		return cache[number][first];
	}
};

Polyomino* polyomino;

int main(void) {

	int* sum;
	cin >> Case;

	polyomino = new Polyomino[Case];
	sum = new int[Case];

	//캐시 초기화
	for (int j = 0; j < 101; j++)
		memset(cache[j], 0, sizeof(cache[j]));

	for (int i = 0; i < Case; i++) {
		polyomino[i].Input();
		sum[i] = 0;
	}

	for (int i = 0; i < Case; i++) {
		//1~전체 갯수만큼 첫줄에 올 수 있으므로 반복 호출
		for (int j = 1; j <= polyomino[i].getNum(); j++) { 
			sum[i] += polyomino[i].countPoly(polyomino[i].getNum(), j);
			sum[i] %= mod;
		}
		cout << sum[i] << endl;
	}
}

문제 풀이

 1. 문제 해결 전략

• 정사각형의 개수 n이 주어지면 반복문을 통해 첫줄에 first(1~n)개 사각형을 배치하고 다음 재귀 함수에 n-first개의 정사각형을 인자로 넘긴다. 호출된 재귀 함수에서 또 반복문을 통해 첫 줄을 채우고 재귀 함수를 호출한다.

• 첫 줄에 first개만큼의 사각형을 배치하고 두 번째 줄에 second개만큼의 사각형을 배치할 때 2번째 줄의 사각형은 처음 1개 겹칠 때 ~  마지막 1개 곂칠때까지 first+second-1개의 세로 단조인 폴리오미노를 만들 수 있다. 

first=3 second=2 인 경우 4개의 폴리오미노가 만들어진다.

 2. cache 설정

• cache[number][first] : number개의 정사각형이 주어졌을 때 첫 줄에 first개만큼의 정사각형을 배치할 경우 만들 수 있는 폴리오미노의 개수

 3. 기저 사례

• cache값이 계산되었으면 바로 반환

 4. 함수 탈출 조건

• number == first인 경우 주어진 정사각형을 가로 한 줄로 배치한 경우로 더 이상 재귀를 호출할 수 없으므로 1 반환

 5. 점화식

•  cache[number][first] += countpoly(number-first, second) -> first+second-1만큼 호출

  -> number개의 사각형 중 첫 줄에 first만큼 배치하면 두 번째 줄(second)는 num-first만큼 올 수 있다.

  -> 두번째줄에 놓을 정사각형 개수가 결정되었다면 first+second-1만큼의 폴리오미노를 만들 수 있다.