백준 22968, 균형

개요

문제 링크
골드 5, DP
왼쪽, 오른쪽의 subtree의 높이차가 1 이하인 binary tree의 최대 높이

---

접근

1. 재귀적 성질을 잘 활용하면 되는 문제, 난 AVL tree가 뭔지 모른다. 그만큼 몰라도 충분히 풀 수 있다.
2. 높이가 k인 트리를 생각하자. 이 트리의 높이가 균형을 이루려면 왼쪽, 오른쪽 subtree가 균형을 이루어야 한다. 그런데 그리디하게 생각해서, 가장 높은 트리를 만들려면 왼쪽과 오른쪽 트리의 높이가 1차이 나는 것이 좋다.
3. 왼쪽이 높다고 가정하면, 높이가 k인 트리의 왼쪽 subtree는 k-1 균형트리, 오른쪽 subtree는 k-2균형 트리가 된다.
4. 이제 dp를 사용해보자. dp[k]를 높이가 k인 트리를 만드는데에 필요한 최소 정점수 라고 하자. 그럼 왼쪽에는 k-1 균형트리, 오른쪽에는 k-2 균형트리가 있으니 dp[k] = dp[k-1]+dp[k-2]가 되고, 둘을 이어줄 정점이 하나 필요하므로 +1을 해주면 된다.
5. 아하 피보나치랑 유사한 문제였구나. 이제 n에 대해 가장 정점이 많이 필요한 높이부터, 정점의 개수가 n보다 작거나 같아지면, 즉 n개로 높이 k인 트리를 구성할 수 있으면 k를 출력하면 된다.

---

Pseudo code

dp[n] = V needed for tree with height k

dp[1] = 1, dp[2] = 2
for (i = 3~n)
    dp[i] = dp[i-1]+dp[i-2]+1
for (i = n~1)
    if (dp[i] <= n)
        return i

---

Source code

#include <iostream>
using namespace std;

#define F 43
int fib[F];
int test() {
    int n;
    cin >> n;
    for (int i=F-1; i; i--)
        if (fib[i] <= n)
            return i;
    return -1;
}

int main() {
    fib[1] = 1, fib[2] = 2;
    for (int i=3; i<F; i++)
        fib[i] = fib[i-1]+fib[i-2]+1;

    int t;
    cin >> t;
    while(t--)
        cout << test() << "\n";
}