이분탐색/삼분탐색 #2805: 나무 자르기

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

2805번: 나무 자르기

 

 

---

 

메모

 

앞서 푼 #1654 랜선자르기 문제와 흡사한 문제이다.

이 문제를 이해하면 어렵지 않게 풀 수 있음

 

 

 

 

 

 

코드

 

 

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

public class Main {

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

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer(bf.readLine());
		
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		int[] arr=new int[N];
		
		long max=0;
		
		st=new StringTokenizer(bf.readLine());
		for(int i=0;i<N;i++) {
			arr[i]=Integer.parseInt(st.nextToken());
			if(arr[i]>max) {
				max=arr[i];
			}
		}

		max++;
		
		long min=0;
		long mid=0;
		
		while(min<max) {
			
			mid=(min+max)/2;
			
			long length=0;
			
			for(int i=0;i<N;i++) {
				if(arr[i]-mid>0){
					length+=(arr[i]-mid);
				}
			}
			
			if(length<M) {
				max=mid;
			}
			else {
				min=mid+1;
			}
			
		}
		System.out.println(max-1);
	}
}