BOJ 2805 나무 자르기 [Java]

문제

BOJ 2805 나무 자르기

접근방법

• 이진탐색 문제이다
• 기준을 정하는 것만 해결하면 쉽다.

구현

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

class Main {
    static int N; // 나무의 수
    static long M; // 가져가는 나무의 길이
    static long[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine(), " ", false);
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new long[N];

        st = new StringTokenizer(br.readLine(), " ", false);
        long max = -1;
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, arr[i]);
        }

        long start = 0;
        long end = max;

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

            sum = getSum(mid);

            if (sum >= M) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        bw.write(end + "");
        bw.close();
    }

    static long getSum(long h) {
        long sum = 0;
        for (int i = 0; i < N; i++) {
            long tmp = arr[i] - h < 0 ? 0 : arr[i] - h;
            sum += tmp;
        }

        return sum;
    }
}

제출