★★뮤직비디오(결정알고리즘)

 

import java.util.*;

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

        n = kb.nextInt();
        m = kb.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(solution(m, arr));
    }

    //DVD의 최소용량크기를 결정해서 이분탐색하기
    private static int solution(int m, int[] arr) {
        int answer = 0;

        //dvd가 9개일 때 최소 용량 크기는 9가 되야 한다.
        int start = Arrays.stream(arr).max().getAsInt();
        //dvd가 1개일 때 용량 크기는 45가 되야한다.
        int end = Arrays.stream(arr).sum();

        while(start<=end) {
            //중간점을 dvd 최소 용량 크기로 결정
            int mid = (start+end) / 2;
            System.out.println(mid);
            //해당 용량으로 dvd에 모두 담을 수 있다면 dvd 용량 낮춰보기
            //1장, 2장으로도 담기면 안돼! 용량 더 낮춰서 m장 맞춰야함
            if(dvdCount(mid, arr) <= m){
                answer = mid;
                end = mid-1;
            }
            //m장으로 담을 수 없으면 절대 안돼! dvd 용량을 더 키워!
            else {
                start = mid+1;
            }
        }

        return answer;
    }

    private static int dvdCount(int mid, int[] arr) {
        //dvd 갯수
        int count = 1;
        //곡들의 합
        int sum = 0;
        for(int i = 0; i < arr.length; i++) {
            sum += arr[i];
            //용량 초과하면 dvd 새로운걸로 변경
            if(sum > mid) {
                count++;
                sum = arr[i];
            }
        }
        System.out.println("count : " + count);
        return count;
    }

}

결정 알고리즘 - 답을 정해놓고 범위에 따라 답을 좁혀나가는 알고리즘

이 문제가 왜 이분 검색으로 풀 수 있는지를 알아야한다.

DVD의 최소 용량크기를 mid로 두고 좁혀 나갈 것임

노래는 N곡 있고 M개의 DVD에 녹화를 하는데, DVD의 크기를 최소로 해야 한다.

1장의 DVD에 녹화를 해야할 수도 있으니 rt의 최댓값은 곡들을 모두 합한 값(45)

9장의 DVD에 녹화를 해야할 수도 있으니 lt의 최솟값은 곡들 중 노래 길이가 가장긴 곡(9)

이분 검색으로 M개의 DVD로 녹화하는 시간들 중 최소의 DVD 길이를 구할 수 있도록 최적화해 나가야한다.

 

용량에 따른 dvd의 갯수 count 메서드를 정의해서 count에 따라 탐색 범위를 결정할 수 있도록할 것

count = 3면 해당 dvd 용량에 노래들을 담을 수 있다. (최소 용량인지는 더 탐색해봐야 암)

count < 3면 노래를 너무 많이 담은 것 - dvd 용량을 줄여야하는 것 

count > 4면 DVD 용량이 부족해서 dvd 용량을 더 늘려야하는 것

 

첫번째는 DVD의 용량(mid)을 한장에 9+45/2 = 27씩 설정하고했을 때이다.

DVD의 갯수 cnt = 2 -> 3보다 작다는 의미는 하나의 DVD에 노래들을 너무 크게 담았다는거다.

(1,2,3,4,5,6) (7,8)

DVD의 담기는 용량(mid)을 줄여서 DVD 갯수가 3개가 될 수 있도록 담을 것임

lt = 9 / rt = 27-1 = 26 (왼쪽 탐색)

 

두번째는 DVD의 용량을 한장에 9+26/2 = 17씩 담는다고 했을 때이다.

DVD의 갯수 cnt = 3 

DVD 용량을 17이라고 했을 때 노래들이 DVD 3장 안에 담길 수 있다. 일단 answer에 대입.

(1,2,3,4,5) (6,7) (8,9)

최소 DVD 길이를 구하는 것이므로 DVD 용량을 더 줄여서 노래들을 담을 수 있는지 확인해봐야한다!

lt = 9 rt = 17-1 = 16 // answer = 17 (왼쪽 탐색)

 

세번째는 DVD의 용량을 한장에 9+16/2 = 12 씩 담는다고 했을 때이다.

cnt = 4 > 3 DVD 용량이 부족해서 3장으로는 노래들을 넣을 수가 없다.

(1+2+3+4) (5,6) (7) (8)

lt = 12+1 rt = 16 (오른쪽 탐색)

 

네번째는 DVD의 용량을 한장에 13+16/2 = 14 씩 담는다고 했을 때이다.

cnt = 4 > 3 DVD 용량이 부족해서 3장으로는 노래들을 넣을 수가 없다.

(1+2+3+4) (5,6) (7) (8)

lt = 14+1 rt = 16 (오른쪽 탐색)

 

다섯번째는 DVD의 용량을 한장에 15+16/2 = 15 씩 담는다고 했을 때이다.

(1+2+3+4+5) (6+7) (8) (9)

cnt = 5 > 3 DVD 용량이 부족해서 3장으로는 노래들을 넣을 수가 없다.

lt = 15+1 rt = 16 (오른쪽 탐색)

 

여섯번째 DVD의 용량을 한장에 16+16/2 = 16 씩 담는다고 했을 때이다.

(1+2+3+4+5) (6+7) (8) (9)

위와 동일

lt = 16+1 rt = 16 -> while문 탈출하여 answer = 17