백준 / 2805 / 나무 자르기 / java

package K이분탐색;

import java.util.Scanner;
import java.util.Arrays;
public class 나무자르기 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        int[] tree = new int[n];

        for(int i=0; i<n; i++){
            tree[i] = sc.nextInt();
        }
        sc.close();
        long start = 0, end = Arrays.stream(tree).max().getAsInt()+1;

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

            long cut = 0;
            for(long i:tree){
                if(i > mid){
                    cut += i - mid;
                }
            }

            if (cut < m){
                end = mid;
            } else {
                start = mid + 1;
            }
        }

        System.out.println(start -1);
    }
    
}

이분 탐색의 Upper Bound 방식으로 해결하는 알고리즘

Upper Bound는 이분탐색으로 최대값을 구할 때 사용된다.
이 문제는 절단할 나무의 최대 값을 구해야 하는 문제이므로 Upper Bound 방식으로 해결해야한다.

Upper bound에서 주의 할 점은 end는 max 값에서 +1로 구해야하며 start - 1 로 답을 구한다는 점이다.

예전에 python으로 풀 때는 lower, upper 개념도 모르고 그냥 코드를 외워서 풀었었다. 그러다 보니 이분탐색에서 새로운 문제를 만나게 되면 start와 end를 어떻게 바꿀지, 정답으로 start, end, mid 어떤걸로 해야하는지 알 수 없었다.

이번에 풀면서 다행이 이러한 개념을 알게되었다.