BOJ 4457 상근이의 자물쇠

BOJ 4457 상근이의 자물쇠

[분류 : 다이나믹 프로그래밍]

  독특한 문제

 

[풀이]
  [경우의 수] 트리를 구성할 때 트리 자체의 높이 h를 고정했다고 보자. 그러면 그 높이 h에서 n개의 노드를 배치해야 한다. h를 만드려면 현재 루트가 되는 노드를 제외한 두 서브 트리 중 하나가 반드시 높이 h-1를 가져야한다. 또 조건에서 두 서브 트리의 높이 차이는 1이하이어야 하므로 경우의 수는 세가지가 나온다.

1. 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-1
2. 왼쪽 서브 트리의 높이가 h-1, 오른쪽 서브 트리 높이가 h-2
3. 왼쪽 서브 트리의 높이가 h-2, 오른쪽 서브 트리 높이가 h-1

  [기저 사례] 기저 사례로는 h가 -1일 때 남은 노드의 수 n이 0이어야만 경우의 수로 포함시키도록 한다. 또 h가 -2이거나(2. 3. 케이스로 인해 -2가 나올 수 있음) h는 -1이 아닌데 n이 0이면 구성할 수 없는 트리이므로 0을 반환해주자.

 

  [최대 높이] 이젠 높이가 문제다. 최대 높이는 포화 이진 트리를 생각하면 최대 10까지 올라가지만, 포화 이진 트리가 아니더라도 높이를 쌓을 수 있다. 따라서 트리를 구성할 때마다 높이를 쌓을 때마다 최소한의 노드를 사용하여 최대 높이를 구성하도록 한다.

  높이 h-2인 트리를 최소한의 노드로 구성했을 때, h를 구성하기 위해서는 대충 h-2에서 사용된 노드의 수 + 2개만큼 더 필요하다. 즉, h-2인 트리를 하나 복사하고, 루트로 둘 노드를 생성하고 그 루트에 왼쪽, 오른쪽 자식에 이어붙힌 뒤, 마지막 것을 두 서브트리 중 리프의 자식으로 넣어두는 것이다. 이렇게 계산하면 높이는 18이상이 될 수 없음을 증명할 수 있다.

  ※ 높이 h를 h-2를 구성하기 위한 노드의 수로 정확히 구하기 어렵기 때문에 최소라고 가정하고 진행한 것. 사실상 노드의 수가 더 필요하기 때문에 최대 높이는 17보다 작다.

#include<cstdio>
#include<cstring>
using ll = long long;
const int MAX_H = 18, MAX_N = 1428, MOD = 1e9;
int dp[MAX_H][MAX_N];
int rec(int h, int n) {
    if (h == -1) return !n;
    if (h == -2) return 0;
    if (!n) return 0;
    int& ret = dp[h][n];
    if (ret != -1) return ret;
    ret = 0;
    int i;
    for (i = 0; i < n; i++) {
        ret = (ret + (ll)rec(h - 1, i) * rec(h - 1, n - 1 - i)) % MOD;
        ret = (ret + (ll)rec(h - 1, i) * rec(h - 2, n - 1 - i)) % MOD;
        ret = (ret + (ll)rec(h - 2, i) * rec(h - 1, n - 1 - i)) % MOD;
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof dp);
    int N, ans, h;
    while (scanf("%d", &N) == 1) {
        ans = 0;
        for (h = 0; h < MAX_H; h++)
            ans = (ans + rec(h, N)) % MOD;
        printf("%09d\n", ans);
    }
    return 0;
}