[백준] 8916 이진 검색 트리

문제 링크

http://icpc.me/8916

8916번: 이진 검색 트리

풀이

3 2 5 4 1 6라는 예제가 있을 때 가장 앞에 나오는 3은 루트 노드로 순서가 바뀔 수 없다는 사실은 조금만 생각해본다면 알 수 있다.

그럼 2 5 4 1 6를 3의 왼쪽 트리와 3의 오른쪽 트리로 나눌 수 있다.

3보다 작은 2 1은 왼쪽 트리가 3보다 큰 5 4 6은 오른쪽 트리가 될 것이다.

그렇다면 재귀적으로 2 1과 5 4 6은 각각 트리가 되고, 첫 번째 수는 루트가 될 것이다.

여기서 조금 더 관찰해 본다면, 같은 모양의 트리가 나오기 위해서는 작은 것들과 큰 것들의 순서들만 유지하면 된다.

어차피 왼쪽 트리와 오른쪽 트리는 첫번째 수보다 큰지 작은지로 결정되기 때문이다.

그렇기 때문에 중복 조합을 이용하여 각각의 경우의 수를 구할 수 있다.

고등학교 이후로 중복 조합을 처음 써서 공식을 까먹어서 오랜만에 중복 조합 공식을 찾아봤다.

nHr = n+r-1Cr

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) int((x).size())

constexpr int MOD = 9'999'991;
int arr[22], n;
ll dp[22][22];

ll com(int n, int r) {
    if (n < r || r < 0) return 0;
    if (n == r || r == 0) return dp[n][r] = 1;
    if (dp[n][r]) return dp[n][r];
    return dp[n][r] = com(n - 1, r - 1) + com(n - 1, r);
}

ll solve(int s, int e) {
    if (s + 1 >= e) return 1;
    vector<int> hi, lo;
    for (int i = s + 1; i < e; i++) {
        if (arr[i] > arr[s]) hi.push_back(arr[i]);
        else lo.push_back(arr[i]);
    }
    for (int i = 0; i < sz(lo); i++) arr[i + s + 1] = lo[i];
    for (int i = 0; i < sz(hi); i++) arr[i + s + 1 + sz(lo)] = hi[i];
    ll l = solve(s + 1, s + 1 + sz(lo));
    ll r = solve(s + 1 + sz(lo), e);
    ll mcom = com(sz(hi) + sz(lo), sz(hi));
    return (((l * r) % MOD) * mcom) % MOD;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int tc; cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 0; i < n; i++) cin >> arr[i];
        cout << solve(0, n) << "\n";
    }
}