기타 레슨 2343

https://www.acmicpc.net/problem/2343

블루레이의 저장용량(시간)에 따라 블루레이의 개수가 달라진다
개수와 m 을 비교해서 중간값을 찾아간다.

코드의 방향은 맞게 구현했는데 틀린부분은
left 값 세팅을 0 으로 하면 틀린다

만약
2 2
1 9
가 주어졌는데 1이 나올것이다 left를 0으로 세팅하였다면
하지만 정답은 9이다
1이면 블루레이2장에 강의를 모두 담을 수 없다

시간복잡도
강의개수 X 이분탐색(강의개수X강의분량)
N log(100000)

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        int[] arr = new int[n];

        input = br.readLine().split(" ");
        int left = 0;
        for(int i = 0; i < n; ++i)
        {
            arr[i] = Integer.parseInt(input[i]);
            left = Math.max(left, arr[i]);//최소한의 값은 가장 긴 강의를 블루레이에 담을 수 있을 만큼 커야한다.
        }

        int right = 10000 * n;//강의최대 길이 * 강의개수
        int cand = 0; //시간
        int ans = 0;
        //평가는 블루레이개수

        while(left <= right)
        {
            cand = (left+right)/2;
            if(cal(arr, cand) > m)
            {
                left = cand+1;
            }
            else
            {
                ans = cand;
                right = cand-1;
            }
        }

        System.out.println(ans);
    }
    public static int cal(int[] arr, int cand)
    {
        int ret = 1;
        int sum = 0;
        for(int i = 0; i < arr.length; ++i)
        {
            sum += arr[i];
            if(sum > cand)
            {
                sum= arr[i];
                ret++;
            }
        }

        return ret;
    }
}