[백준] 2805 : 나무 자르기 - java [자바]

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

2805번: 나무 자르기

 

 

이 글은 이분탐색을 이미 알고있는 사람을 대상으로 작성한다.

• 이분탐색을 이용해 최적의 값을 찾아낸다.
• 이분탐색 문제에서는 구해야하는 값을 찾고 해당 값을 기준으로 풀이한다. 보통 정답을 요구하는 값과 일치한다.
• 해당 문제에서는 K(절단기에 설정할 높이의 최댓값)이 기준 값이다.
• 따라서 변화하는 K를 기준으로 totalSlicedHeight(잘려진 나무 길이의 합)이 M(가져가야할 나무 길이)보다 부족할 때는 K를 감소시키고
• totalSlicedHeight가 M보다 클 때는 K를 증가시킨다.
• K에 대한 이분탐색이 종료되면 탐색된 K값을 출력한다. 이분탐색이 종료되는 조건은 start > end 이다.

코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class 나무_자르기_2805 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        String[] input = br.readLine().split(" ");

        int N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);

        List<Integer> woodList = new ArrayList<>();

        int maxHeight = 0;

        for (String wood : br.readLine().split(" ")) {
            int woodHeight = Integer.parseInt(wood);
            woodList.add(woodHeight);
            maxHeight = Math.max(maxHeight, woodHeight);
        }


        long start = 0;
        long end = maxHeight;

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

            long totalSlicedHeight = 0;

            for (Integer woodHeight : woodList) {
                long slice = woodHeight - mid;
                if (slice > 0) {
                    totalSlicedHeight += slice;
                }
            }

            if (totalSlicedHeight < M) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }

        bw.write(Long.toString(end));

        bw.close();
        br.close();
    }
}