백준 2343: 기타레슨 - 이분탐색(Parameter Searche) C++

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

2343번: 기타 레슨

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;


int N, M;
vector<int> lecture;

bool canMakeBlueray(ll lim){
    int cnt = 0;
    int sum = 0;

    for(int i=0; i<N; i++){
        sum += lecture[i];

        if(sum == lim){
            sum = 0;
            cnt++;
        }
        else if(sum > lim){
            sum = lecture[i];
            cnt++;
        }
    }

    if(sum>0) cnt++;
    return cnt <= M;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    int maxNum = 0;
    for(int i=0; i<N; i++){
        int num;
        cin >> num;
        lecture.push_back(num);
        maxNum = max(maxNum, num);
    }


    //각 강의는 10000분을 넘지 않기 때문
    //100000 * 10000 -> long long
    ll st = 1, en = N*10000;


    while(st<=en){
        ll mid = (st+en)/2;

        if(mid >= maxNum && canMakeBlueray(mid)){
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }

    cout << st <<'\n';
    
    return 0;
}