백준 22968번 균형 - C++(cpp) 풀이

---

 

1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자.
2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-1) + f(h-2) + 1
3. f(h) ≤ V인 h 중 최댓값을 찾는다.

 

1. f(h) = 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값이라고 하자.

 AVL 트리에서는 모든 부분 트리가 AVL 트리이다. 따라서 재귀적인 방법을 떠올릴 수 있다. 먼저 높이 h짜리 AVL 트리를 만들기 위해 필요한 노드 개수의 최솟값을 f(h)라고 정의하자.

 

2. 노드 수를 최대한 줄이기 위해서는 두 자식 트리의 높이를 각각 h-1, h-2로 만들어주어야 하므로 f(h) = f(h-1) + f(h-2) + 1

 먼저 두 자식 트리 중 적어도 하나는 h-1의 높이를 가져야 한다. 그리고 노드 수를 최소화하기 위해서는 남은 자식 트리의 높이를 최대한 작게 만들어주면 된다. 두 자식 트리의 높이 차가 1 이하여야 하므로 최소 h-2의 높이를 가지게 할 수 있다. 따라서 f(h) = f(h-1) + f(h-2) + 1이 된다. 마지막 1 값은 루트 노드 한 개 값이다.

 

3. f(h) ≤ V인 h 중 최대값을 찾는다.

 예제 입출력을 통해 V = 10^9의 범위 내에서는 h가 최대 42밖에 되지 않는다는 것을 알 수 있다. 따라서 h=1부터 반복문을 차례로 돌면서 f(h) ≤ V를 만족하는 h의 최댓값을 구해주어도 시간 초과가 발생하지 않는다.

반응형

---

#include <iostream>
#include <string.h>

using namespace std;

typedef long long ll;

int T, V;
ll cache[44];

// 높이 height짜리 AVL tree를 만들기 위한 최소 노드 개수
ll min_num_of_vertex(int height) {
    if (height == 1) return 1;
    if (height == 2) return 2;
    
    ll& ret = cache[height];
    if (ret != -1) return ret;
    
    return ret = min_num_of_vertex(height-1) + min_num_of_vertex(height-2) + 1;
}

int find_max_height(int v) {
    for (int i=1; i<44; i++) {
        if (min_num_of_vertex(i) > v) return i-1;
    }
    
    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    memset(cache, -1, sizeof(cache));

    cin >> T;
    while (T--) {
        cin >> V;
        cout << find_max_height(V) << "\n";
    }

    return 0;
}