boj 2805: 나무 자르기

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다.

이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

=> 최소의 최대를 구하는 문제는 뭐다?? = 이분탐색이다~~

 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		long length = in.nextLong();
		long tree[] = new long[n];

		long start = 0;
		long end = 0;
		for (int i = 0; i < n; i++) {
			tree[i] = in.nextLong();
			end = Math.max(end, tree[i]);
		}

		long answer = 0;
		while (start <= end) {
			long mid = (start + end) / 2;
			// System.out.println(start + " " + answer + ", " + mid + " " + end);
			if (sumTree(mid, tree) >= length) {
				answer = Math.max(mid, answer);
				start = mid + 1;
			} else {
				end = mid - 1;
			}
		}
		System.out.println(answer);
	}

	private static long sumTree(long cut, long[] trees) {
		long sum = 0;
		for (long tree : trees) {
			sum += tree >= cut ? tree - cut : 0;
		}

		return sum;
	}
}