[BOJ_2805 | Binrary Search] 나무 자르기

풀이

이분 탐색을 통해 문제를 해결하면 주어진 시간 안에 문제를 해결하는 알고리즘을 구현할 수 있다.

먼저 주어진 나무들의 길이를 배열에 저장하고 Arrays.sort를 통해 빠르게 길이순으로 정렬한다.

이분탐색의 탐색범위는 0부터 길이가 가장 긴 나무의 길이까지이며(left = 0, right = arr[arr.length-])

mid 는 0부터 시작해 반복문의 매번 마지막에는 (left+right)/2 로 재설정해준다.

각각의 반복문이 돌아갈 때마다

또 다른 반복문을 통해 mid의 길이에 따른 잘린 나무들의 길이의 합을 구해준다.

이 길이가 m과 같으면 mid의 값을 출력하고, 아닌 경우 각각 mid의 값을 갱신하여 반복문을 돌게 한다.

하지만 한 가지 주의해야 할 점이 있는데

문제의 조건을 잘 살펴보면, 높이가 H인 절단기로 나무를 절단했을때, 

그 길이들의 합이 반드시 m이 나오지 않는 경우가 생길 수 있다는 것이다. 

이 경우 위와 같은 알고리즘으로는 답을 구할 수 없다.

그래서 아래와 같은 식을 추가했다.

if(dis > sum - m && sum > m){
    dis = Math.abs(sum - m);
    dismin = mid;
}

dis 라는 변수는 sum과 m의 차이가 최소가 될 때의 mid값을 저장할 수 있도록 sum과 m의 차이의 최솟값을 저장하고,

이때의 mid의 최솟값을 dismin이라는 변수에 저장한다.

이렇게 하면, sum == m이 되지 않아 아무런 출력 없이 while반복문을 빠져나오게 되는 경우에도

dismin값을 출력해줌으로써 문제를 해결할 수 있게 된다.

소스 코드

import java.util.*;
import java.io.*;
public class BOJ_2805 {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<n;i++){ arr[i] = Integer.parseInt(st.nextToken()); }
        Arrays.sort(arr);
 
        //Binary Search
        int left = 0; int right = arr[arr.length-1];
        int mid = 0; long dis = Integer.MAX_VALUE;
        int dismin = 0; boolean flag = false;
        
        while(left<=right){
            long sum = 0;
            for(int i=0;i<arr.length;i++){
               if(arr[i] > mid) sum += arr[i]-mid;
            }
 
            if(dis > sum - m && sum > m){
                dis = Math.abs(sum - m);
                dismin = mid;
            }
 
            if(sum>m){ left = mid+1; }
            else if(sum<m){ right = mid-1;}
            else{
                bw.write(mid+"\n");
                flag = true;
                break;
            }
            mid = (left+right)/2;
        }
        if(!flag)bw.write(dismin+"\n");
        bw.flush();
        bw.close();
    }
}