[PS] BOJ2805 나무 자르기 ( BinarySearch ) with JAVA

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

2805번: 나무 자르기

 

◎ 문제풀이

 

여러 개의 나무를 동일한 크기로 잘랐을 때, 자투리로 남는 나무를 가져가는 문제이다. 원하는 만큼의 나무를 가져가려면 어느 정도 동일한 크기로 잘라야 할까? 

 

자르는 크기를 h라고 하면 h는 1 부터 가장 큰 나무의 크기 사이에 있다. 범위 안에서 적절한 값을 구하는 문제인데, 나무의 크기가 1 ≤ M ≤ 2,000,000,000 이므로 엄청나게 범위가 넓다. 큰 범위에서 탐색이므로 이분탐색을 이용하여 시간복잡도를 줄여보자. 

 

[PS] BOJ1654 랜선 자르기 ( BinarySearch ) with JAVA

 

위 문제도 이분탐색문제이다. 위 풀이와 다른 점이 있다면, '랜선 자르기' 문제는 근삿값을 구하는 문제가 아니라 최댓값을 구하는 문제였다. 그래서 원하는 크기가 나와도 계속 탐색을 하여 최댓값을 구했다. 반면, '나무자르기' 문제는 근삿값을 구하는 문제로 탐색중 원하는 크기가 나오면 바로 return하면 된다. 

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

import static java.lang.Math.*;

//BOJ2805 나무 자르기
public class Bs2 {

    static int[] woods;
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        woods = new int[n];

        int maxHigh = 0;
        for(int i =0;i<n;i++){
            woods[i] = Integer.parseInt(st.nextToken());
            maxHigh = max(maxHigh,woods[i]);
        }

        int left = 1;
        int right = maxHigh;
        
		//이분탐색 시작
        while(left <= right) {
            int mid = (left+right)/2;
            long remain = getWoodRemain(mid);
            if ( remain > m) left = mid+1;
            else if(remain < m ) right = mid-1;
            else{ // 검색 중 원하는 값이 나오면 바로 return
                System.out.println(mid);
                return;
            }
        }
        System.out.println(right);
    }

    public static long getWoodRemain(int mid){
        long remain = 0;
        for (int wood : woods) {
            if( wood > mid ) remain += wood-mid;
        }
        return remain;
    }
}