[백준] 2805번 : 나무 자르기

랜선 자르기

---

해결 방법

주어진 시간은 1초인데 N과 M의 범위가 매우 크다.
그래서 완전탐색으론 해결할 수 없다.

-> 이분 탐색을 사용하자

주어진 범위와 문제 형태를 보고, 이분 탐색을 사용해야 할지 구별하는 능력을 키워야 할 것 같다.

이분 탐색을 기반으로한 Upper Bound를 사용해서 해결했다.
Upper Bound는 '원하는 값 k를 초과한 값이 처음 나오는 위치를 찾는 과정'이라고 할 수 있다.

비슷한 개념인 LowerBound는 '원하는 값 k 이상이 처음 나오는 위치를 찾는 과정' 이다.

---

코드

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

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());
        List<Long> arr = new ArrayList<>();

        st = new StringTokenizer(br.readLine()," ");
        for(int i=0; i<n; i++) {
            arr.add(Long.parseLong(st.nextToken()));
        }

        long min = 0;
        long max = Collections.max(arr);

        System.out.println(binary_search(m,min,max,arr));

    }
    public static long binary_search(int m,long min, long max, List<Long> arr){
        long mid=0;
        while(min<max){
            //중간 값 (= 자르는 위치)
            mid = (min+max)/2;
            long sum =0;

            for(Long tree : arr){
                //나무의 크기가 자르는 위치보다 작다면 = 음수
                if(tree-mid > 0){ //나무의 크기가 자르는 위치보다 커서 잘린다면 = 양수라면
                    //sum 변수에 잘린 나무의 길이 다 더함.
                    sum += (tree-mid);
                }
            }

            //잘린 나무의 길이를 모두 더한 값이 원하는 값보다 작다면?
            //=자르는 위치가 높다 -> 자르는 위치를 낮춰야 함.
            //max를 줄여야 한다.
            if(sum < m)
                max = mid;

            //잘린 나무의 길이를 모두 더한 값이 원하는 값보다 크다면?
            //=자르는 위치가 낮다 -> 올리자.
            //min을 올려야 한다.
            else{
                min = mid + 1;
            }
        }
        //m와 sum이 같아지면 min을 높여서 반환해서 1을 빼서 반환해야 함.
        return min-1;
    }
}