[JAVA] 백준 2805 나무 자르기_이분탐색

 

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

 

 

접근 : 

 

 - 정답이 있을 수 있는 범위내로 left, right 를 설정 후 이분 탐색을 실행한다.

 

 - 예상 답안이 목표하는 값 이상일 때, left를 mid + 1 로 이동시킨다.

 

 - 예상 답안이 목표하는 값 미만일 때, right를 mid - 1 로 이동시킨다.

 

 - left <= right 까지 실행시키면 마지막 값 target 이상 자를 수 있는 최대 높이이다.

 

 

 

코드구현 : 

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().split(" ");
        int n = Integer.parseInt(temp[0]);
        int m = Integer.parseInt(temp[1]);

        String[] inputs = br.readLine().split(" ");
        List<Integer> nums = new ArrayList<>();

        for(int i = 0; i < n ; i++) nums.add(Integer.parseInt(inputs[i]));

        int left = 0;
        int right = 2_000_000_000;
        int mid = 0;
        int answer = 0;
        double temp_res = 0;

        while(left <= right){
            temp_res = 0;
            mid = (left + right) / 2; 

            for(int num : nums) temp_res += num > mid ? (num - mid) : 0;
            
            if(temp_res >= m){
                answer = mid;
                left = mid + 1;
                continue;
            }
            right = mid - 1;
        }
        
        System.out.println(answer);
        br.close();
    }
}