백준 - 2805번 나무 자르기 - java

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);
	}
}