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

풀이>
결정알고리즘 : 답이 어떤 값들 사이에 있다는것이 확실할 때 사용하는 알고리즘
DVD의 최소길이는 예시에서 곡 1개의 최대길이인 9와 곡 전체의 합인 45사이에 있는 것이 확실하므로 9~45를 범위로 생각하고 이분검색을 지속하여 최적의 답을 찾아내는 방법

import java.util.*;
public class Main {
    public int count(int[] arr, int capacity) {
        int cnt = 1, sum=0; //cnt -dvd 장수
        for (int x : arr) {
            if (sum + x > capacity) {
                cnt++;
                sum = x;
            }else sum +=x;
        }
        return cnt;
    }
    public int solution(int n, int m, int[] arr) {
        int answer = 0;
        int lt = Arrays.stream(arr).max().getAsInt();
        int rt = Arrays.stream(arr).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 void main(String[] args) {
        Main T = new Main();
        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();
        }
        System.out.println(T.solution(n, m, arr));
        }
}