Treejin's Note

문제 설명

• 폴리오미노 : 정사각형들의 변들을 서로 완전하게 붙여 만든 도형
• 세로 단조 폴리오미노 : 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않는 폴리오미노
• 폴리오미노를 구성하는 정사각형의 개수 n이 주어진다.(1 <= n <= 100)

=> n개의 정사각형으로 구성된 세로 단조 폴리오미노의 개수를 10,000,000으로 나누어 출력하기

문제 풀이

한 줄에 놓이는 정사각형의 개수

세로 단조 폴리오미노, 어떤 가로줄도 폴리오미노를 두 번 이상 교차하지 않으려면

가로 한 행에 놓여진 정사각형들이 모두 붙어있어야 한다는 의미이다.

따라서 한 줄에 n개, n-1개, n-2개,....,1개를 놓고

그 아래줄에 n-1개, n-2개, ... , 1개를 놓고

...

이런 식으로 진행하면 된다.

각각을 작은 문제로 쪼개면

한 줄에 놓을 수 있는 정사각형의 개수 n을 받은 후, 그중 a개를 놓고, 그 다음줄에 n-a개를 넘겨주는

재귀함수로 표현할 수 있다.

정사각형들의 위치

한 줄에 놓을 정사각형의 개수를 정했다면,

어떤 위치에 놓아야 하는지도 중요하다.

각 정사각형의 변은 붙어있어야 하므로 윗줄과 아랫줄이 완전히 분리되어서는 안된다.

윗 줄이 2칸, 아랫 줄이 3칸이라고 했을 때 배치할 수 있는 경우의 수는 다음 그림과 같다.

a + b 에 완전히 분리되는 1가지 경우를 제외한 a + b - 1의 경우의 수가 발생한다.

즉, b개의 정사각형을 배치한 후 윗줄에 놓여진 정사각형의 개수를 참고하여 연산한 값을 반환해야 한다.

메모이제이션

남은 정사각형의 개수가 같다면 놓여질 수 있는 경우의 수도 같다.

이에 대한 중복연산을 방지하기 위해 메모이제이션에 연산 결과를 저장하여 사용할 수 있다.

문제 풀이 코드

// for (int i = leftCnt; i > 0; --i) 0ms
// for(int i = 1; i <= leftCnt; ++i) 4ms

#include <iostream>
#include <string.h>

#define DIVNUM 10000000

using namespace std;

int memoization[101][101];

int makePolyomino(int top, int leftCnt) {	// top : 이전 줄에 배치된 정사각형 개수, leftCnt : 남은 정사각형 개수
	int& ret = memoization[top][leftCnt];
	if (ret != -1) {
		return ret;
	}

	if (leftCnt == 0)
		return ret = 1;

	ret = 0;
	//for(int i = 1; i <= leftCnt; ++i){
	for (int i = leftCnt; i > 0; --i) {		// i : 이번 줄에 배치할 정사각형 개수
		ret += (makePolyomino(i, leftCnt - i) * (i + top - 1)) % DIVNUM;
		ret %= DIVNUM;
	}

	return ret;	// 메모리에 담겨져 다른 경우에 활용 가능해지는 시점
}

int main() {
	int C;
	cin >> C;
	memset(memoization, -1, sizeof(memoization));
	for (int tc = 1; tc <= C; ++tc) {
		int n;
		cin >> n;
		int sum = 0;
		//for(int i = 1; i <= n; ++i){	// i : 맨 윗줄에 놓을 정사각형
		for (int i = n; i > 0; --i) {
			sum += makePolyomino(i, n - i) % DIVNUM;
		}
		cout << sum % DIVNUM << endl;
	}
	return 0;
}

참고

메모이제이션 & 재귀 호출 순서에 대한 속도 차이

문제를 풀다가 궁금한 점이 생겼다.

n, n-1, n-2, ... , 1 순서대로 배치하는 것과 1, 2, 3, ... , n 순서대로 배치하는 것에 시간차이가 발생할까?

순서를 바꾸어서 답안을 제출해본 결과,

n, n-1, n-2, ... , 1로 연산한 결과가 0ms

1, 2, 3, ... , n으로 연산한 결과가 4ms가 나왔다.

이는 메모이제이션에 저장하는 시점으로 인한 차이이다.

n이 5라고 가정할 때, n, n-1, n-2, ... , 1 방식은

(5) -> (4,1) -> (3,2) -> (3,1,1) -> (2,3) -> ... 순서로 재귀가 진행될 것이다.

이 때, 메모이제이션되는 시점은 밑줄이 쳐진 부분. 즉, 연산의 끝에 도달한 순간부터 거꾸로 진행된다.

하지만 1, 2, 3, ... , n 방식에서는

(1,1,1,1,1) -> (1,1,1,2) -> (1,1,2,1) -> (1,1,3) -> (1,2,1,1) -> ... 순서로 재귀가 진행되는데,

1,1에 대한 연산이 이미 중복되어 진행된 후에 메모리에 담기므로

중복연산을 줄여주는 메모이제이션의 역할이 많이 발휘되지 못한다.

따라서 메모리에 담기는 시점을 고려하여 재귀 순서를 결정하는 것도

시간 단축에 있어 도움이 된다는 것을 배웠다!