[BOJ 2805번] 나무 자르기(JAVA)

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

2805번: 나무 자르기

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

class Main{
   
   static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
   static int answer;
   
   public static void main(String args[]) throws Exception {
	   String s[]=br.readLine().split(" ");
	   int N=Integer.parseInt(s[0]);
	   int M=Integer.parseInt(s[1]);
	   String s1[]=br.readLine().split(" ");
	   int arr[]=new int[N];
	   for(int i=0;i<N;i++) {
		   arr[i]=Integer.parseInt(s1[i]);
	   }
	   Arrays.sort(arr);
//	   for(int i=0;i<arr.length;i++) {
//		   System.out.print(arr[i]+" ");
//	   }
	   int right=arr[N-1];
	   int left=0;
	   while(right>=left) {
		   long sum=0;
		   int mid=(left+right)/2;
		   answer=mid;
		   for(int i=arr.length-1;i>=0;i--) {
			   if(arr[i]-mid>=0) sum+=arr[i]-mid;
			   else break;
		   }
		   if(sum>M) left=mid+1;
		   else if(sum<M) right=mid-1;
		   else {
			   System.out.println(mid);
			   return;
		   }
	   }
	   System.out.println(right);
   }
}

절단기의 높이를 이분탐색으로 찾아보았습니다.

여기서 판단 조건은 잘린 나무의 합이 M보다 큰지 작은지였는데요, M과 같을 때는 그 자리에서 코드를 종료시켜 바로 정답을 출력하도록 설정했습니다.