링크

링크텍스트

문제

풀이

대표적인 이분탐색 문제이다.
탐색해야 되는 범위가 상당히 크기 때문에 for문으로 하나하나 탐색하지 못할때 이분탐색을 사용한다.
이분탐색 흐름은
1. 정렬한다.
2. 초기값 start와 나무의 최댓값을 end로 지정한다.
3. while문을 반복하면서 start값과 end값을 설정해서 찾는다 (이 문제는 나무길이의 최대값이기 때문에 end값을 뽑아내야 한다.)

이 문제에서 주의해야 할 점은 int형 범위를 벗어나기 때문에 long형을 사용해야 한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

// 2805 나무자르기
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = br.readLine().split(" ");

        int n = Integer.parseInt(arr[0]);
        long m = Long.parseLong(arr[1]);

        List<Long> list = new ArrayList<>();
        arr = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            list.add(Long.parseLong(arr[i]));
        }

        Collections.sort(list);

        long start = 0;
        long end = list.get(list.size() - 1);

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

            long sum = 0;
            for(int i=0;i<list.size();i++){
                long element = list.get(i);

                if(mid < element){
                	//자르고 남은 길이를 sum에 저장
                    sum += element - mid;
                }
            }


            //자른 길이가 들고 가야 할 길이보다 더 길다면 start값을 늘려 mid값을 더 크게 설정할 수 있도록
            if(sum >= m){
                start = mid + 1;
            } else{
                end = mid - 1;
            }
        }

        System.out.println(end);
    }

}