[JAVA / 백준 : 2805] 나무자르기

조건

높이의 길이가 1,000,000,000보다 작거나 같은 양의 정수이기때문에 long타입을 써야하는 문제

sum 을 int로 지정해놔서 계속 틀렸다.

 

import java.util.Arrays;
import java.util.Scanner;

public class 나무의수 {

	public static void main(String[] args) {
		
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int M = scan.nextInt();
		long[] array = new long[N];

		for (int i = 0; i < N; i++) {
			array[i] = scan.nextLong();
		}
		Arrays.sort(array);
		
		long left = 0;
		long right = array[N - 1];
		while(left <= right) {
			long middle =(right + left) / 2;
			long sum = 0;
			for(long tree : array) {
				if(tree > middle)
					sum += (tree - middle);
			}
			if(sum >= M) {
				left = middle + 1;
			}
			else 
				right = middle - 1;
		}
		System.out.println(right);
		scan.close();
	}
}