2805

 

나무자르기 : https://www.acmicpc.net/problem/2805

 

 

나무의 길이 H와 비교해야할 값 M의 관계가 반비례이다.

연산도중, 범위가 int를 초과하면 오류가 발생하므로 long을 사용해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N, M;
	static boolean DBG = false;
	static int[] arr;

	public static void main(String[] args) throws IOException {

		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 < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());

		long lt = 1;
		long rt = Arrays.stream(arr).max().getAsInt();
		long hMax = 0;
		while (lt <= rt) {
			long mid = (rt + lt) / 2;
			//M보다 수확한 나무의 길이가 크거나 같을 때, 값이 유효하다.
			//H가 늘어날 수 록 M은 줄어든다. (반비례)
			if (M <= check(arr, mid)) { 
				if (DBG)
					System.out.printf("<=%d %d mid : %d\n", lt, rt, mid);
				hMax = Math.max(hMax, mid);
				lt = mid + 1;
			} else {
				if (DBG)
					System.out.printf(">%d %d mid : %d\n", lt, rt, mid);
				rt = mid - 1;
			}
		}

		System.out.println(hMax);
	}

	static long check(int[] list, long h) {
		long m = 0;
		for (int i = 0; i < list.length; i++) {
			if (h < list[i])
				m += list[i] - h;
		}
		if(DBG)
		System.out.println("m : " + m);
		return m;
	}

}