취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 2392번 문제인 다각형의 분할이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/2392 

고정된 볼록다각형을 삼각형으로 분할하는 방법의 경우의 수는 카탈란 수와 같다는 것은 잘 알려져있다.

볼록다각형을 사각형으로 분할한다면 어떨까?

글쓴이는 다음과 같은 관찰을 통해 점화식을 세웠다.

1. 먼저 다각형의 한 변을 골라 고정한다.

2. 이 한 변을 포함하는 사각형의 대변(마주보는 변)을 결정한다면, 처음 고정한 변을 제외한 나머지 세 변들에 대하여 그 변 방향쪽에 남아있는 꼭짓점의 개수를 세는 것으로 꼭짓점의 개수가 적어진 부분 문제를 찾을 수 있게 된다.

위 점화식을 정리하고 초기값을 적절히 정해 잘 구현해주자.

아래는 제출한 소스코드이다.

#define MOD 1000000000
#include <iostream>
using namespace std;
typedef long long ll;

ll T[1001];
ll Q[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	ll N; cin >> N;

	//삼각분할
	T[2] = T[3] = 1;
	for (int k = 4; k <= 1000; k++) {
		for (int i = 2; i < k; i++) {
			T[k] = (T[k] + T[i] * T[k + 1 - i]) % MOD;
		}
	}

	T[2] = 0;

	//사각분할
	Q[0] = Q[2] = Q[4] = 1;
	for (int k = 6; k <= 1000; k += 2) {
		for (int L = 2; L < k; L += 2) {
			for (int R = L; R < k; R += 2) {
				Q[k] = (Q[k] + ((Q[L] * Q[R - L + 2]) % MOD) * Q[k - R]) % MOD;
			}
		}
	}

	Q[0] = Q[2] = 0;

	cout << T[N] << '\n' << Q[N];
}