SWERC 2019 J. "Counting Trees"

algorithm-ps ― [ swerc-2019 , BOJ ]

SWERC 2019 J번 문제이다. BOJ 18302번이기도 하다.

대회 중에는 rkm0959가 풀었다. 너무 긴 본문이 읽기 싫어서 알큼이 요약해준 문제 설명대로만 코드를 짰다가 중요한 디테일을 누락시켜서 엄청 고생했다…

간단히 말해서, inorder traversal (LDR 순회)이 주어진 수열이 나올 수 있는 binary tree의 개수를 구하는 문제이다. 단, 이 tree는 min-heap의 조건 (자식 \(\ge\) 부모)를 만족해야 한다.

Solution

CP에서 보기 드문 적당한 난이도의 괜찮은 조합론 문제인 것 같다.

크기 \(n\)의 unlabeled binary tree의 개수는 \(n\)-th Catalan number \(C_{n}\)개임이 알려져 있다. 일반성을 잃지 않고 노드에 적힌 값들을 \(0, \cdots, x\)라고 해보자.

우선 \(0\)이 적힌 노드 (\(0\)-노드)들이 루트를 포함하는 연결된 이진 트리를 이룸을 관찰할 수 있다. 이러한 이진 트리의 개수는 Catalan Number 개수가 되고, 각각의 경우에 대해 수열의 나머지 원소들이 어떤 \(0\)-노드의 서브트리로 들어가는지가 자동으로 결정된다. 따라서 \(0\)-노드들에 의해 분할된 수열에서 재귀적으로 문제를 풀면 된다.

시간복잡도 \(\mathcal{O}(n \log n)\)을 유지하려면 구현이 좀 까다롭다. 수열의 원소들을 linked-list 형태로 저장하고, 같은 수가 적힌 두 노드가 다른 구간에 속하는지 판정하기 위해 구간 합 Segment Tree를 하나 유지해주면 된다.

Written on March 5, 2020