[JAVA] 알고리즘 : 정렬- 뮤직비디오(결정 알고리즘)

import java.util.*;



public class Main{
    public int count(int[] arr, int capacity){
        // dvd의 한장 용량을 capacity로 했을 때
        // dvd가 몇장 필요한지 리턴
        int cnt=1; // dvd 장 수
        int sum=0; // 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; // mid를 dvd한장의 용량으로 결정
            if(count(arr,mid)<=m){ // dvd장 수가 m보다 작거나 같으면
                answer=mid;
                rt=mid-1; // 범위 좁히기
            }
            else lt=mid+1; // 큰 쪽을 검사
        }
        return answer;
    }
    public static void main(String[] args) {
        Main T = new Main();
        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();
        System.out.println(T.solution(n, m, arr));
    }
}