백준 - 2805번 나무 자르기

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

추가적인 테스트 케이스

@paa0609 님
2 11
10 10
정답 : 4

3 1
1 2 2
정답 : 1

@wjsqjawns님
4 10
1 4 5 7
정답:
2

5 2000000000
900000000 900000000 900000000 900000000 900000000

정답: 500000000

1 1000000000
1000000000
답: 0

1 1
1000000000
답: 999999999

출처: https://joey09.tistory.com/113 [joie de vivre]

접근법

이분탐색으로 min = 0, max = 최대값으로 지정해놓고 반씩 잘라가며 탐색
범위가 크므로 변수를 int형으로 하면 오버플로우나서 에러나므로 long형으로 설정

소스

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] h = new int[n];
		long MAX = 0;
		long MIN = 0;
		for(int i = 0; i < n; i++) {
			h[i] = sc.nextInt();
			MAX = h[i] > MAX ? h[i] : MAX;
		}
		long height = 0;
		while(MIN <= MAX) {
			height = (MAX + MIN) / 2;
			long sum = 0;
			for(int i = 0; i < h.length; i++) {
				if(h[i] - height > 0) sum += h[i] - height; 
			}
			//더 많이 잘라야하므로, 높이를 낮춰야함 = 아래쪽 탐색
			if(sum < m) {
				MAX = height - 1;
			} else if(sum >= m){
				//덜 잘라야하므로, 높이를 올려야함 = 위쪽탐색
				MIN = height + 1;
			} 
		}
		System.out.println(MAX);
	}
}