[BOJ]2805_나무자르기

--문제--

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

2805번: 나무 자르기

--문제접근--

나무자르기는 대표적으로 이분탐색의 문제로 이분탐색을 구현하여서 문제풀이를 진행하였습니다. 하지만 또 INT형으로 문제를 계속 풀다보니 답이 틀렸다고나와서 LONG형으로 바꿔 문제풀이를 진행하여보니 문제가 풀렸습니다.

package 백준문제풀이;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

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));
		StringBuilder sb=new StringBuilder();
		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);
		long ans=0;
		long start=0;
		long end=arr[N-1];
		long mid=0;
		while(start<=end) {
			mid=(start+end)/2;
			long cnt=0;
			for(int i=0;i<N;i++) {
				long temp=arr[i]-mid;
				if(temp>0)cnt+=temp;
			}
			if(cnt>=M) {
				ans=mid;
				start=mid+1;
			}
			else end=mid-1;
		}
		sb.append(ans);
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

}