[JAVA] 백준 2805 - 나무 자르기

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] arr = new int[ n];

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr);

        int left = 0;
        int right = arr[n-1];
        int answer = 0;
        while(left<=right){
            int mid = (right+left)/2; // 절단기 설정 높이
            long sum = 0;
            for(int height : arr){
                if(height > mid) sum += height - mid; // 절단기 설정 높이보다 나무의 높이가 크면 그 차이만큼을 집에 들고 감
            }
            if(sum < m){ // 집에 들고가는 나무높이가 m보다 작으면
                right = mid-1; // 집에 들고가는 나무 높이(절단기 설정 높이와 나무 높이의 차)를 늘리려면 절단기 설정 높이를 낮춰야 함
            }else{ // 집에 들고가는 나무 높이가 m보다 크거나 같으면
                left = mid+1; // 절단기 설정 높이를 높임
               // answer = Math.max(answer, mid); // 집에 가져갈 수 있으므로 최댓값 갱신
            }
        }
        System.out.println(right);
    }
}