설명

지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.

DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.

순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는

1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.

지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.

고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.

그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.

코드

public class MusicVideo {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int input2 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }
        int solution = solution(input1, input2, arr);
        System.out.println(solution);
    }
    public static int solution(int n, int m, int[] arr){
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt();   //max()가 반환하는 값은 OptionalInt를 반환하므로 getAsInt로 int로 변환해주어야함, 배열의 max()로 최대값을 받음
        int rt = Arrays.stream(arr).sum();              //sum()으로 배열의 합을 받음
        while(lt<=rt){
            int mid = (lt+rt)/2;
            if(count(arr, mid) <= m){
                answer = mid;
                rt = mid-1;
            }else{
                lt = mid+1;
            }
        }
        return answer;
    }
    public static int count(int[] arr, int capacity){
        int cnt = 1;
        int sum = 0;
        for(int x : arr){
            if(sum+x>capacity){
                cnt++;
                sum=x;
            }else{
                sum+=x;
            }
        }

        return cnt;
    }
}

이번 문제는 나한텐 많이 어려웠다... 결정 알고리즘이란 개념을 처음 접해봤기 때문이였는데. 지금까지 이분 검색을 사용하여 문제를 풀어왔기 때문에 이분 검색을 사용할거라 생각은 해서 문제에 접근까진 좋았었던거 같다. 하지만 어떻게 반복문을 종료시킬지에 대한 조건과 어떻게 카운트를 할지를 몰랐다. 나는 배열 자체에서 이분 검색을 실행하여 문제를 풀이하려고 했었고 예시 문제는 어떻게 답이 나왔긴 했지만 문제에 직접 넣어서 돌려보니 다 오답 처리 되더라... 그래서 강의를 들어보니 배열 자체에서가 아닌 배열의 값들을 활용하여 새로운 기준을 갖고 풀었어야했다ㅜㅜ

그래도 다행인건 풀이는 이해가 가더라...

결정 알고리즘 : 이분 검색을 활용하여 답을 어떻게 찾는지에 대한 알고리즘

다음 문제도 결정 알고리즘인데 강의를 듣지않고 내 힘으로 꼭 풀어보자