[알고리즘] 백준 - 나무 자르기

백준 - 나무 자르기

내 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;


public class baekjoon_2805 {

    static int N, M;
    static int[] trees;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] inputs = br.readLine().split(" ");
        N = Integer.parseInt(inputs[0]);
        M = Integer.parseInt(inputs[1]);
        trees = new int[N];
        inputs = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            trees[i] = Integer.parseInt(inputs[i]);
        }

        int left = 0;
        int right = 1000000000;
        int check = 0;
        while (left <= right) {
            int mid = (left + right) / 2;

            long cuttedTree = cutTree(mid);
            if (cuttedTree >= M) {
                check = mid;
                left = mid + 1;
                continue;
            }

            if (cuttedTree < M) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        System.out.println(check);
    }

    private static long cutTree(int mid) {
        long treeSum = 0;
        for (int i = 0; i < N; i++) {
            if (trees[i] >= mid) {
                treeSum += trees[i] - mid;
            }
        }
        return treeSum;
    }
}

이분탐색의 대표적인 문제인데 처음보면 헷갈리는 부분들이 조금 있다. mid는 결국 절단기의 높이를 의미한다. 잘려진 나무가 필요양보다 많으면 mid를 올려야하고, 부족하면 내려야한다.

1. 범위를 재조정하기 전에 조건을 만족하면 체크
2. 범위를 재조정하는 방법 알기