[이진탐색] 나무자르기

백준 2085 나무자르기

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

package com.company;
import java.util.*;
import java.io.*;


public class Main {

    public static void main(String[] args) throws Exception {

        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt( st.nextToken() );
        int M = Integer.parseInt( st.nextToken() );

        int maxHeight=-1;

        int[] tree = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
            if(maxHeight < tree[i]) maxHeight=tree[i];
        }
        System.out.println(checkHeight(tree, M, maxHeight, 0));
    }


    //이진탐색을 통해 가장 최대 나무절단 높이를 찾음
    private static int checkHeight(int[] tree, int M, int high, int low) {

        int bestHeight = 0;
        int mid;

        while (low <= high){
            mid = (low+high)/2;
            long wood = calWood(tree, mid);

            if(wood==M){
                bestHeight = mid;
                break;
            }else if(M < wood){
                bestHeight = mid;
                low = mid+1;
            }else if(wood < M){
                high = mid-1;
            }
        }
        return bestHeight;
    }


    //절단하고 얻을 수 있는 나무의 양
    private static long calWood(int[] tree, int cutHeight){

        long woodSum=0;
        for(int i=0; i<tree.length; i++){
            if(cutHeight < tree[i]){
                woodSum += tree[i] - cutHeight;
            }
        }
//        System.out.println(cutHeight +"에서 자르고 " + woodSum + "얻음");
        return woodSum;
    }
}

이진탐색 이용.

값의 범위가 int의 범위가 넘지 않도록 주의.

단일 값은 괜찮지만 합이 int의 범위를 넘을 수 있다는 걸 빼먹어서 시간을 소비. (woodSum)