[Baekjoon Online Judge] 2805번: 나무 자르기

2805번: 나무 자르기

요구사항

 - 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다.

 - 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다.

 - 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구한다.

입력

 - 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

 - 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

 - 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

---

1. 입력받은 나무들을 정렬하기

2. 절단기의 높이 만큼 잘라가며 start 높이를 올리거나 end 높이를 낮춰감

3. start와 end 높이가 교차할 때 까지 반복하여 절단기의 높이를 조정

 

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

public class Baekjoon2805 {

    static int n, m;
    static int[] trees;

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bufferedReader.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        m = Integer.parseInt(input[1]);

        trees = new int[n];
        int max = 0;

        input = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(input[i]);
            max = Math.max(max, trees[i]);
        }

        Arrays.sort(trees);

        long start = 0;
        long end = max;

        while (start <= end) {
            long mid = (start + end) / 2;
            long sum = 0;

            for (int tree : trees)
                if (tree > mid) sum += tree - mid;

            System.out.println("start : " + start + 
            " | end : " + end + 
            " | mid : " + mid + 
            " | sum : " + sum); // 디버깅

            if (sum >= m) start = mid + 1;
            else end = mid - 1;
        }

        System.out.println(end);
        bufferedReader.close();
    }
}