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를 하나 유지해주면 된다.