티스토리 뷰

삼각분할

문제 설명

문제 : 백준온라인저지(BOJ) 7737 삼각분할

다각형이 주어졌을 때 삼각형으로 분할 할 수 있는 경우의 수를 구하는 문제다.

5각형은 아래 그림1 처럼 5가지 방법으로 삼각분할 할 수 있다.

그림1그림1

n각형을 삼각 분할하는 경우의 수를 이라 할 때 을 주어진 값 M으로 나눈 나머지를 출력해야한다.


Solution

이 문제는 유명한 카탈란 수 문제이다. 왜 뜬금 없이 카탈란 수가 삼각 분할하는데 나왔을까? 추론 과정을 따라가보자.

아래 그림2 처럼 오각형의 각 변에 2, 3, 4, 5로 숫자를 표시하고 오각형의 대각선으로 추가되는 새로운 변에 나머지 두 변에 적힌 수의 곱을 표시하도록 하자. 여기서부터 직관적으로 n각형을 삼각분할 하는 것이 n-1개 항의 이항 연산 순서를 결정하는 경우의 수를 구하는 것과 같은 문제임을 알 수 있다.

그림2그림2

따라서 이제 삼각분할 문제가 아니라 이항 연산 순서를 결정하는 문제를 풀도록하자. 이항 연산은 이진 트리로 나타낼 수 있다. 5각형 삼각 분할과 대응되는 아래 곱셈 순서를 각각 이진 트리로 나타내보자.

이항 연산을 트리로 나타냄이항 연산을 트리로 나타냄

잘 관찰해보면 n개 항을 가지는 이항 연산 순서를 결정하는 경우의 수는 다시 leaf 노트가 n개인 이진 트리를 구성하는 경우의 수와 같음을 알 수 있다.

자식 노드가 없는 노드를 leaf (잎)노드라고 한다.

leaf 노드가 n개인 이진 트리를 구성하는 경우의 수를 이라 할 때 는 다음과 같은 식으로 나타낼 수 있다.

이는 카탈란 수 의 점화식 과 동일하다.

따라서 n각형을 삼각 분할하는 경우의 수는 카탈란 수 와 동일하다. 이제 삼각 분할은 생각하지 말고 카탈란 수를 구하는 것에 집중하자.

카탈란 수의 일반항은 이므로 다음 항과의 관계식 를 얻을 수 있다. 그럼 이 관계식을 이용해서 을 구하면 문제를 다 푼 걸까?

중간 과정에서 n이 100만 되도 순식간에 long long int 값의 범위를 넘어가기 때문에 을 구하는 중간 과정에서 계속 모듈러 연산(나머지 연산)을 하면서 진행해야한다. 그런데 을 진행하면서 이미 중간에 M으로 나머지 연산을 한 상태이기 때문에 n+2를 나눌 때 나누어 떨어지지 않을 수 있다.

M이 소수라는 보장이 있으면 n+2를 나누는 대신 모듈러 역원을 곱하면 되지만 M은 2이상 10억 이하의 정수이므로 소수라는 보장이 없다. 이를 해결하기 위해 소수를 leaf 노드에 대응시킨 뒤 곱셈 인덱스 트리를 구성하고 관계식에서 곱셈하거 나누는 수를 소인수분해한 뒤 나타난 소인수들을 인덱스트리에서 증감 시켜주고 인덱스트리를 업데이트하는 방식을 이용한다.




Code

소수는 seive 함수 안에서 에라토스테네스 체를 통해 구했고 소인수 분해를 쉽게 하기 위해 에라소트테네스 체를 진행하면서 정수 j의 소인수를 factor[j]에 저장했다.

소수를 leaf노드로 하는 곱셈 인덱스트리는 struct BinaryTree로 구현했다.


댓글
최근에 달린 댓글
Total
Today
Yesterday