조건

N개의 강의가 순서대로 나열된다. 그리고 이 순서는 바뀔수가 없다.
강의를 블루레이로 녹화하여 M개의 블루레이로 담으려한다
M개의 블루레이의 크기는 다 같아야하고 블루레이 크기가 어떨떄 최소일까를 구하는 문제이다.

내가 생각한 방법

전의 문제와 비슷하게 이분탐색으로 접근하면된다.
물론 값이 작을경우에는 n2 으로 브루트포스를 하면 될꺼라 생각했지만 1<=N <= 10만이라는 범위를 가지고 있다. 10만 * 10만을 하게 되면 10000000000 으로 1억보다 말도 안되게 커버리게 되어서 시간제한이 날것이다.

하지만 기준을 정하고 이분탐색을 한다면 시간초과는 안날것이다.
우리는 크기에 따라 몇개를 고를수 있는지 정할수있다

저번 문제와 다르게 최소를 1로 잡게되면 1,2,3,,,,,9 가 있을때 1말고는 고를수가 없게된다. 그렇기에 입력받은 값중 최대값을 low 인 최소값으로 잡아야한다 그렇기에 최소일때 모든 값을 선택할수 있게 되기 때문이다.
그렇게 최소값일때는 N개의 블루레이를 만들수있다

그리고 최대값은 모든 입력받은 값을 더한 값이다. 그러면 최대값일때 1개의 블루레이를 만들수 있기 때문이다.

그렇게 이 블루레이 크기를 줄이고 늘려나감에 따라 블루레이의 개수가 정해진다.
그래서 최소와 최대값의 값중 중간값을 정하고 그값에 따른 블루레이 개수가 작으면 값을 줄여주어 블루레이 개수를 늘려주고 블루레이 개수가 작으면 값을 늘려 개수를 늘려주면 된다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N,M;
int low=-987654321,high,temp,mid;
int count_T,ret;
vector<int> v;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> N >> M;
    
    for(int i=0;i<N;i++) {
        cin >> temp;
        low=max(temp,low);
        high+=temp;
        v.push_back(temp);
    }
    
    while(low<=high) {
        mid=(low+high)/2;
        count_T=1;
        temp=0;
        
        for(int a:v) {
            temp+=a;
            if(temp>mid) {
                count_T+=1;
                temp=a;
            }
        }
        
        if(count_T<=M) {
            ret=mid;
            high=mid-1;
        }
        else {
            low=mid+1;
        }
    }
    
    cout << ret << "\n";
    
    return 0;
}

현재 입력받은 값들중에서 mid 를 통해서 블루레이 개수를 정한다.
count_T 가 블루레이의 개수이다 이값이 크고 작냐에 따라 값을 줄이고 늘려 최적의 값을 찾으면 된다.

틀렸던 이유

값을 더하면서 현재의 블루레이 개수를 선택하는것은 성공했지만 더한 값이 mid 와 같을때 한번 더 더해지는 오류를 발견했다. 그리고 최소값을 1로 선택한것이 잘못이다.
이분탐색으로 풀땐 확실하게 최소와 최대를 생각하고 풀어야한다.