알고리즘-뮤직비디오(결정알고리즘, 이분탐색)

문제

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

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는
1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 
이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.


입력
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다.
다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다.
부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.


출력
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.

접근

우선 문제를 풀기전 이분탐색에 대해서 개념이 많이 부족했기 때문에 어려운 부분도 있었다.
이분탐색법에 대해 다시 공부를 하고 풀었지만 어떤 방법으로 이분탐색을 써야할지 적용에 대한 문제를 파악해내지 못했고 결국 해답을 참고하였다.

우선 위의 그림처럼 요청되어 나눠져야 하는 M개의 DVD의 갯수를 최대로하여 나눈 후 그값들의 묶음 중 최대값(묶음 최대값이 결국 필요 최소 용량크기와 같음)을 구해야 한다.

1. 필요한 최소 DVD용량을 startPoint로 잡는다. => 1개의 최소 dvd는 배열의 모든 값을 하나는 넣을 수 있는 크기어야 한다. 그말은 즉, 배열안의 최댓 원소를 startPoint로 설정해야한다.

2. 필요한 최대 DVD용량을 endPoint로 잡는다. => 모든 배열의 값을 합쳤을 때 그것을 하나로 묶을 수 있는 크기어야 한다. 그말은 즉, 배열의 모든 값의 합을 endPoint로 설정해야한다.

위의 그림과 같이 startPoint는 최댓값 9 , endPoint는 모든 원소의 합 45로 설정했다.

mid값이 27인 상태로 count를 하는 함수를 진행한다. => dvd묶음의 27(mid)이하가 되면서 묶음이 몇개가 되는지 체크를한다.

예를들면, (1+2+3+4+5+6+7) 묶었을때, 28이 되므로 그 전까지 (1+2+3+4+5+6)으로 묶고
1개를 카운트한다.
이후, (7+8+9)가 24이므로 1개의 묶음을 더 카운트한다. 
총 묶음은 2개가 되므로 요구사항인 M(3)이하다.

현재 answer값은 27

한번 실행후

다시 mid값이 17이 되고 count 함수를 실행한다.
(1+2+3+4+5) / (6+7) / (8+9) => 전부 mid(17)이하이면서 M(3)개 이하이다.

현재 answer = 17이 된다.

다시 반복문 실행

(1+2+3+4) / (5+6) / (7) / (8) / (9) => mid(13)이하로 나눴지만
count 5개 요구사항 M(3)보다 많이 나눠졌다.

M보다 많기 때문에 answer는 17 그대로 유지하고, sp를 9 +1 = 10으로 변경되어
반복문을 실행한다.

이런식으로 쭉 반복문을 실행하다보면 startPoint > endPoint가 됐을때 반복문을 빠져나오면 된다.

코드

package Problem;

import java.util.Arrays;
import java.util.Scanner;

public class 뮤직비디오2 {

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

        int N = sc.nextInt();
        int M = sc.nextInt();
        int arr[] = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        solution(arr, M);
    }
    public static void solution(int arr[], int M){
        //DVD한개의 최소 크기는 가장 큰 길이의 배열의 원소 이상이어야한다. 왜냐하면 메모리의 크기가 배열중 최대 원소보다 작다면 적재가 안됨
        //DVD한개의 최대 크기는 모든 원소들의 합보단 작아야함 크더라도 최솟값을 구하기 때문에 필요없는 크기임
        int start = Arrays.stream(arr).max().getAsInt();
        int end = Arrays.stream(arr).sum();
        int answer = 0;

        while(start <= end){
            int mid = (start+end) / 2;

            //나눈 갯수 체크 M보다 작아야함
            if(nanugi(arr, M, mid)<=M){
                //System.out.println(nanugi(arr, M, mid));
                    answer = mid;
                    end = mid - 1;
                //System.out.println(mid);
            }else{
                start = mid + 1;
            }
            //System.out.println(start+", "+end);
        }

        System.out.println(answer);

    }

    public static int nanugi(int arr[], int M, int mid){
        int sum = 0;
        int count = 1;

        for(int i=0; i<arr.length; i++){
            sum += arr[i];
            if(sum > mid){
                //System.out.println("sum : "+sum+", mid : "+mid);
                count++;
                sum = arr[i];
            }
        }
        //System.out.println("카운트 : "+count);
        return count;
    }

}