[백준] 2805 나무 자르기 [java]

문제

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

풀이법

이분탐색 문제로, 톱의 높이를 이분탐색하여 답을 찾으면 된다.
이때 시작은 start = 0, end = 나무 중 가장 높은 것의 높이 로 하고,
만약, mid로 자른 나무들이 목표보다 길거나 같으면 start = mid + 1,
만약, mid로 자른 나무들이 목표보다 짧으면 end = mid - 1 로 한다.

중요한 점

나무의 길이와 정확히 일치하는 지점을 찾는게 아니라, 최소 길이를 만족하는 최대 높이를 찾는 것이기 때문에, >=, <= 이 들어갈 곳과, 마지막에 mid를 출력해야 하는지, start, end를 출력해야 하는지 잘 생각하면서 풀어야 한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 나무 적어도 m미터 가져가는데 필요한 절단기 최대 높이
public class Boj2805 {
//public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int treeNum = Integer.parseInt(stringTokenizer.nextToken());
        int goalLength = Integer.parseInt(stringTokenizer.nextToken());
        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int[] tree = new int[treeNum];
        for(int i = 0 ; i < treeNum; i++){
            tree[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
        Arrays.sort(tree);

        int maxHeight = tree[tree.length - 1];
        long currLength = 0;

        int start = 0, end = maxHeight, mid = 0;
        while(start <= end){

            mid = (start + end) / 2;
            currLength = 0;

            for(int i = 0; i < tree.length; i++){
                if(tree[i] > mid) currLength += tree[i] - mid;
            }

            if(currLength < goalLength){
                end = mid - 1;
            }
            else if(currLength >= goalLength){
                start = mid + 1;
            }
        }

        System.out.println(end);
    }
}