[BOJ] 2805번 : 나무 자르기

코드

import java.io.*;
import java.util.*;

public class Main {

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

    public static void main(String[] args) {
        input();
        func();
        System.out.println(result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        trees = new int[n];

        sc.nextLine();

        int i = 0;
        for (String s : sc.nextLine().split(" ")) {
            trees[i++] = Integer.parseInt(s);
        }

        sc.close();
    }

    static void func() {
        int left = 0;
        int right = 1_000_000_000;

        while (right >= left) {
            int mid = (left + right) / 2;

            // 나무를 mid 높이에서 자를 때, 원하는 길이 이상의 나무를 얻을 수 있으면
            // 더 높은 높이에서 잘라도 원하는 길이 이상을 얻을 수 있는지 탐색해봐야 한다.
            if (getTotalLength(mid) >= m) {
                result = mid;
                left = mid + 1;
            } else {
                // 원하는 길이 미만의 나무를 얻을 수 있으면
                // 더 낮은 높이에서 자를 경우를 탐색해봐야 한다.
                right = mid - 1;
            }
        }
    }

    // 나무를 cut 높이에서 자를 때, 얻을 수 있는 나무의 길이를 구하는 함수
    static long getTotalLength(int cut) {
        long sum = 0L;

        for (int i : trees) {
            if (i > cut) {
                sum += i - cut;
            }
        }

        return sum;
    }
}