[백준] 2805. 수들의합 (Java) [이분탐색]

문제

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

2805번: 나무 자르기

 

알고리즘

이분탐색

 

코드

package com.company;

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

public class Test_BinarySearch2 {
    static int N, M;

    static int MAX = 1000000000;
    static BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<Integer> treeList = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        //입력
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(bf.readLine());
        for (int i = 0; i < N; i++) {
            treeList.add(Integer.parseInt(st.nextToken()));
        }

        go();
    }

    static public void go() throws IOException {
        int left = 1;
        int right = MAX;
        int ans=0;
        while(left<=right){
            int mid = (left+right)/2;
            if(check(mid)<M){
                right=mid-1;
            }else{
                left=mid+1;
                ans= mid;
            }
        }
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }

    static long check(int h) throws IOException {
        long cnt=0;
        for(int i=0; i<treeList.size(); i++){
            if(treeList.get(i)>h){
                cnt+=treeList.get(i)-h;
            }
        }
        return cnt;
    }
}