[백준 JAVA] 22968 : 균형

[백준 22968] 균형 : https://www.acmicpc.net/problem/22968

22968번: 균형

---

문제 조건 정리

 

1. 양의 정수 V 가 주어지면, 최대 V 개의 정점을 사용해서 만들 수 있는 AVL Tree의 최대 높이를 출력하는 프로그램을 작성하자.

높이 균형 만족

 

높이 균형 만족

정점 8에서 높이 불균형

 

---

입력

 

1. 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
2. 둘째 줄부터 T개의 줄에 걸쳐 정점의 개수 V가 한 줄에 하나씩 주어진다.

---

문제를 풀기 전

 

1. 그림을 그려보며 규칙을 쉽게 찾았음!

트리의 최대 높이	필요한 정점의 수 (최소)
1	1 (0 + 0 + 1)
2	2 (0 + 1 + 1)
3	4 (1 + 2 + 1)
4	7 (2 + 4 + 1)
N	N-2 높이를 만드는데 필요한 정점의 최소 수 +  N-1 높이를 만드는데 필요한 정점의 최소 수 + 1

 

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        // 최대 높이 계산
        // V의 최대 입력 값 1_000_000_000로 만들 수 있는 최대 높이 -> 42
        // 1_000_000_000 개의 정점은 높이 41개는 충분히 쌓고 43개는 쌓지 못한다.
        // 트리의 높이(1 ~ 43)을 미리 저장
        int[] maxHeight = new int[44];
        maxHeight[1] = 1;
        maxHeight[2] = 2;
        maxHeight[3] = 4;
        maxHeight[4] = 7;

        for (int i = 5; i < maxHeight.length; i++) {
            maxHeight[i] = maxHeight[i - 2] + maxHeight[i - 1] + 1;
        }

        int t = Integer.parseInt(bufferedReader.readLine());
        StringBuilder stringBuilder = new StringBuilder();

        // 테스트 케이스만큼 반복
        for (int i = 0; i < t; i++) {
            int v = Integer.parseInt(bufferedReader.readLine());

            // 이진 탐색 알고리즘
            int left = 1;
            int right = maxHeight.length - 1; // 43 (저장해둔 트리 높이)

            // 이진 탐색에서 left 가 right 보다 크면 안됨
            while (left <= right) {

                // mid = left + right 와 동일한 값
                // 오버플로우 방지
                int mid = left + (right - left) / 2;

                // 입력된 정점의 개수로 mid 만큼의 높이를 갖는 트리를 만들 수 있다면?
                if (maxHeight[mid] <= v) {

                    // 그리고 입력된 정점의 개수로 (mid + 1) 만큼의 높이를 갖는 트리를 만들 수 없다면?
                    // 즉, 입력된 정점의 개수로는 mid 만큼의 높이를 갖는 트리는 만들 수 있고,
                    // (mid + 1) 만큼의 높이를 갖는 트리는 만들 수 없다.
                    // 조건 만족 -> mid 기록
                    if (maxHeight[mid +1] > v) {
                        stringBuilder.append(mid).append("\n");
                        break;

                    // 그리고 입력된 정점의 개수로 (mid + 1) 만큼의 높이를 갖는 트리를 만들 수 있다면?
                    // mid 값이 커져야한다.
                    // 즉, left 의 증가
                    } else {
                        left = mid + 1;
                    }

                // 입력된 정점의 개수로 mid 만큼의 높이를 갖는 트리를 만들 수 없다면?
                // mid 값이 작아져야한다.
                // 즉, right 의 증가
                } else {
                    right = mid - 1;

                }


            }
        }

        // 결과 출력
        System.out.println(stringBuilder);
    }
}

 

---

문제를 풀고 난 후

 

주어진 정점의 개수로 최대 높이를 구하는 로직을 1에서부터 42(43의 전)까지 순차적으로 찾는 방법을 사용하면서 비효율적이라고 생각해서, 이진 탐색으로 변경했으나 시간, 공간 복잡도가 거의 비슷해서 아쉬웠음!

 

AVL 트리를 공부하고 싶어서 검색해서 푼 문제였는데, 내가 생각한 방향과 달라서 아쉬웠으나 오랜만에 쉽게 푼 dp 문제였음!