백준 6236번 : 용돈 관리 - 이분탐색(매개변수 탐색) C++

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

6236번: 용돈 관리

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


int N, M;
vector<int> cost;


void Input(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        int c;
        cin >> c;
        cost.push_back(c);
    }

}

bool withDraw(ll k){
    int cnt = 0;

    ll curMoney = 0;

    for(int i=0; i<N; i++){
        if(k < cost[i]){
            return false;
        }


        if(curMoney < cost[i]) {
            curMoney = k;
            cnt++;
        }

        curMoney -=cost[i];
    }

    return cnt <= M;
}


ll binarySearch(){
    ll st = 1, en = 100000*10000;

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

        if(withDraw(mid)){
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    return st;
}



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

    Input();
    cout << binarySearch() << '\n';

    return 0;
}