떡볶이 떡 만들기

 

 

import java.util.*;

public class Main {
    //public static int n;
    //public static int m;
    //public static int[][] arr;

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

        //떡 갯수
        int n = kb.nextInt();
        //요청한 떡의 길이
        int m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }

        //제일 긴 떡의 길이
        int max = Arrays.stream(arr).max().getAsInt();

        System.out.println(binarySearch(0, max, m, arr));

    }

    private static int binarySearch(int start, int end, int m, int[] arr) {
        //절단기 높이
        int height = 0;

        while(start <= end) {
            //절단기의 높이를 중간값으로 설정
            int mid = (start + end) / 2;
            //잘린 떡의 길이의 합
            int sum = 0;
            System.out.println("mid : " + mid);

            //절단기로 자르기 실행해야함
            for(int i = 0; i < arr.length; i++) {
                //잘린 떡의 길이 합치기(잘리지 않는 것도 감안해야함)
                if(arr[i] - mid > 0) sum += arr[i] - mid;
            }
            //손님 요청에 부합하면(많이 잘리면) 절단기 높여서 더 많이 잘라
            if(sum >= m) {
                start = mid + 1;
                //제일 마지막에 담긴 값이 최대 높이가 될거다.
                height = mid;
            }
            //요청한 것 보다 덜 잘리면 절단기 낮춰서 더 조금 잘라
            else {
                end = mid - 1;
            }
        }
        return height;
    }
}