[Math] BOJ 8916 이진 검색 트리

문제 링크 : www.acmicpc.net/problem/8916

8916번: 이진 검색 트리

한 트리에서 왼쪽 자식은 모두 파란색, 오른쪽 자식은 모두 빨간색으로 칠해보자.

우선 이러한 형태의 BST(Binary Search Tree)를 구성하기 위해선 반드시 root가 처음 입력되어야 한다는 것은 자명하다.

이 때, root 노드를 제외한 나머지 노드들의 번호가 아예 존재하지 않는다고 가정할 때,

위와 같은 BST의 형태만을 만드는 것은 다음과 같다.

파란색 노드 사이마다 빨간색 노드를 중복으로 넣는 것과 같다.

각 자식 노드들의 서브트리 관계와 상관없이 단지 입력만을 고려했을 때, 

왼쪽 서브트리의 모든 노드와 오른쪽 서브트리의 모든 노드를 나열하는 경우의 수는 중복조합으로 나타낼 수 있다.

앞서 말했듯 이는 노드에 번호를 매기기 전 상태이므로, 서브트리의 root가 먼저 입력되어야 하는 등의 문제는 생각하지 않는다.

 

이제 완전한 경우의 수를 구하려면 나열된 파랑, 빨강 노드들에 대해 번호를 붙여야 한다.

이 번호를 붙이는 경우의 수가 곧 각 서브트리를 새로운 트리로 생각했을 때 재귀적으로 구한 경우의 수가 된다.

즉, 파랑 노드 4개에 대한 번호를 붙이는 경우의 수는 곧 파랑 노드로만 이루어진 서브트리를 전체 트리로 생각할 때의 결과값과 같다.

이러한 서브트리를 또다시 위처럼 왼쪽 자식은 파랑색, 오른쪽 자식은 빨강색으로 칠하며 구하는 것이다.

 

결론적으로, 트리의 모든 노드에 대해, 각 노드의 왼쪽 자식 수를 l, 오른쪽 자식 수를 r이라 하자.

이 때, 경우의 수는 (l+1)Hr = (l+r)Cr 이며, 이 값들을 모두 곱해준 것이 우리가 원하는 답이 된다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <memory.h>
 
#define DIV 9999991
 
using namespace std;
typedef long long ll;
typedef pair<int, int> p;
 
typedef struct {
    int num;
    int lchild = -1, rchild = -1;
    int lcnt = 0, rcnt = 0;
}node;
 
int n;
int seq[20];
vector<node> tree;
 
ll combination(int a, int b) {
    //aCb의 값을 반환
    if (a < b) swap(a, b);
    ll ret = 1, div = 1;
    for (int i = 0; i < b; i++) {
        ret *= (a - i);
        div *= (b - i);
    }
    return (ret / div) % DIV;
}
 
void set_tree(int num) {
    node temp;
    temp.num = num;
 
    int cur = 0;
    while (1) {
        if (tree[cur].num < num) {
            //오른쪽 자식
            tree[cur].rcnt++;
            if (tree[cur].rchild == -1) {
                //빈자리를 찾았다면
                tree[cur].rchild = tree.size();
                tree.push_back(temp);
                break;
            }
            cur = tree[cur].rchild;
        }
 
        else {
            //왼쪽 자식
            tree[cur].lcnt++;
            if (tree[cur].lchild == -1) {
                //빈자리를 찾았다면
                tree[cur].lchild = tree.size();
                tree.push_back(temp);
                break;
            }
            cur = tree[cur].lchild;
        }
    }
}
 
void init() {
    cin >> n;
 
    memset(seq, 0, sizeof(seq));
    tree.clear();
 
    for (int i = 0; i < n; i++) cin >> seq[i];
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    int tc;
    cin >> tc;
 
    for (int t = 0; t < tc; t++) {
        init();
        node root;
        root.num = seq[0];
        tree.push_back(root);
 
        for (int i = 1; i < n; i++) set_tree(seq[i]);
 
        ll answer = 1;
        for (int i = 0; i < tree.size(); i++) {
            ll val = combination(tree[i].lcnt + tree[i].rcnt, tree[i].lcnt) % DIV;
            answer = (answer * val) % DIV;
        }
 
        printf("%lld\n", answer);
    }
 
    //system("PAUSE");
    return 0;
}
 

 

트리의 깊이는 최대 20이 될 수 있는 반면,

실제 노드는 최대 20개이기 때문에 선형 트리로 구현한다면 메모리상으로 매우 비효율적인 구현이 된다.

(시간 초과도 발생하는 것으로 확인)