[백준/Java] 2805 나무 자르기

문제 분석

완전탐색으로 풀기에는 M의 크기와 N의 크기를 곱했을 때 21억을 넘어감으로 불가능하다. 따라서 시간을 최적화해야 되는데, 이분탐색을 적용했다. 절단기의 높이가 0부터 주어진 나무의 최대값까지 선형적으로 있다고 가정하고, 절단기의 높이를 이분탐색을 통해 찾는다.

중간점검을 진행할 때, 절단된 높이의 합과 M의 길이를 비교하여 다음과 같이 min값과 max 값을 변경한다.

• 절단된 높이의 합이 M보다 크거나 같은 경우: min 값을 mid + 1로 갱신
• 절단된 높이의 합이 M보다 작은 경우: max 값을 mid - 1로 갱신

 

주의할 점은 절단된 높이의 합은 int를 초과할 수 있으므로 long으로 선언해줘야 한다.

 

문제 풀이

import java.util.Scanner;

public class Main {

    static int N, M, min, max, mid;
    static int[] lengthOfTrees;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        lengthOfTrees = new int[N];

        for (int i = 0; i < N; i++) {
            lengthOfTrees[i] = sc.nextInt();
            max = Math.max(lengthOfTrees[i], max);
        }

        findMaxHeight();

        System.out.println(max);
    }

    public static void findMaxHeight() {
        while (min <= max) {
            long sumOfCutTree = 0;
            mid = (min + max) / 2;

            for (int i = 0; i < N; i++) {
                if (lengthOfTrees[i] > mid) {
                    sumOfCutTree += lengthOfTrees[i] - mid;
                }
            }

            if (sumOfCutTree >= M) {
                min = mid + 1;
            } else {
                max = mid - 1;
            }
        }
    }
}