문제 설명

문제 분석

슈도코드

구현

public class 블루레이_만들기_2343 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int M = scan.nextInt();
        int[] lessons = new int[N];
        int start = 0;
        int end = 0;
        for (int i = 0; i < N; i++) {
            lessons[i] = scan.nextInt();
            if (start < lessons[i]) {
                start = lessons[i]; // 레슨 최댓값을 시작 인덱스로 저장
                end += lessons[i]; // 모든 레슨의 총합을 종료 인덱스로 저장
            }
        }

        while (start <= end) {
            int middle = (start + end) / 2;
            int sum = 0;
            int count = 0;

            // middle값으로 모든 레슨을 저장할 수 있는지 확인
            for (int i = 0; i < N; i++) {
                if (sum + lessons[i] > middle) {
                    count++;
                    sum = 0;
                }
                sum += lessons[i];
            }

            // 탐색 후 sum이 0이 아니면 블루레이가 1개 더 필요
            if (sum != 0) {
                count++;
            }

            if (count > M) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }

        System.out.println(start);
    }
}