[백준][JAVA]2805번 : 나무 자르기 ( 이분검색 )

---

배열 요소를 변수 하나를 이용해서 계속 반복문 돌리면 역시 시간초과다 .

 

시간을 단축하기 위해서 이분검색을 이용해야 한다.

 

sum < m 이면 , 목표량에 부족하니까 더 많이 잘라야함 -> rt 감소

sum > m 이면 , 목표량보다 많은거니 더 적게 잘라야함 -> lt 증가

 

import java.util.*;
class Main {
    public static void main(String args[]) throws Exception {
        Scanner kb = new Scanner(System.in);
        int n=kb.nextInt();
        int m=kb.nextInt();
        int[] arr=new int[n];

        int lt=0;
        int rt=0;

        // 최저값 lt : 최대값 rt
        for(int i=0; i<n; i++){
            arr[i]=kb.nextInt();
            rt=Math.max(rt,arr[i]);
        }

        while(lt<rt){
            int mid=(lt+rt)/2;
            long sum=0;
            for(int x:arr){
                if(x-mid>0){
                    sum+=x-mid;
                }
            }

            if(sum<m){
                rt=mid;
            }
            else{
                lt=mid+1;
            }
        }
        System.out.println(lt-1);
    }
}