백준 2805번: 나무 자르기 [이분탐색][매개변수탐색][BinarySearch] -Java

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

2805번: 나무 자르기

이분탐색의 응용개념인 매개변수 탐색 알고리즘이 들어간 알고리즘.

 

알고리즘은 잘 풀었으나.. int가 받아주는 최대의 값이 20억정도라는 걸 고려하지 못해  "틀렸습니다"의 쓴맛을 봤다.

결론적으로 sum개념의 calc변수와 diff 변수에만 Long 데이터 타입을 주면 됐다.

 

시간 복잡도는 O(N log N) 이다.

N이 1,000,000이기때문에 최악의 경우에도 1초당 6,000,000 번 연산을 수행한다.

 

 

<Java 코드>

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

public class Main {

	public static int arr[];
	public static int N,M;
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		
		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());
		arr = new int[N];
		
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		//정렬
		Arrays.sort(arr);
		
		//최댓값 저장 변수
		long diff = Long.MAX_VALUE;
		long res = 0;
		
		//이분 탐색
		long start = 0;
		long end = arr[N-1];
		
		while(start <= end) {
			//현재 추정한 X의 값으로 계산해보면(나무를 잘라보면)  M보다 큰가?
			long x = (start+end)/2;
			
			// 전체에 대하여 x를 자르기
			long calc = 0;
			for (int i = arr.length-1; i > -1; i--) {
				if(arr[i] >= x)
					calc += arr[i]-x;
				else 
					break;
			}
			
			if(calc == M) {
				res = x;
				break;
			}else if(calc > M) {
				// X의 범위를 더 키워야함. 낭비가 너무 많음.
				start = x+1;
				
				//현재 가장 유력한 최댓값 갱신
				if(diff > calc-M) {
					diff = calc-M;
					res = x;
				}
			}else {
				// X의 범위를 더 줄여야함. M 최소에도 못미침
				end = x-1;
			}
			
		}
		
//		System.out.println(res);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(res+"\n");
		bw.flush();
	}
	

}