조건

N 일동안 자신이 사용할 금액을 나열하고 그중 M번만 통장에서 돈을 뺴서 쓰기러했다한다.
만약 그날 통장에서 뺸 돈으로 하루를 보낼수 있으면 사용하고 모자라만 다시 집어넣고 K 원을 인출하면된다.

1 <= N <= 100000 , 1<=M <= N

이해

처음에 이 문제가 이해 가지 않았다
그냥 문제 자체가 이해가 안갔다.
내가 이해한 방식은 이렇다

7일 중 100 400 300 100 500 101 400 의 비용을 사용할꺼고 이중에서 M 번을 통장에서 돈을 뺴서 쓴다길래 N중 M 개를 고르는 조합을 사용해야하나? 라고 생각하게 되어 출력인 500이 절대 나오지 않았던 것이다.

하지만 실제로 풀어야하는 방식은 K원씩만 뽑을수 있는것이였어서 처음 500을 가지고 100,400|300,100|500|101|400 이렇게 5번 뽑아야하는것이였다.

접근

사실 당연하게도 이분탐색을 생각하지 않았더라면 1부터 10만까지 처음부터 N까지 돌렸을것이다.
이 방식은 N제곱으로 10만 * 10 만으로 1억 연산이 넘어가게 된다.
그래서 시간을 줄여줄 다른 알고리즘을 선택했어야하는데 나는 이분탐색으로 풀게 되었다.

N 일 동안 나열된 값들중 이분탐색의 최소 조건이 되어야하는것은 N일 중 가장 큰 값이다.
만약 N일중 가장 작은 값을 최소 조건으로 사용하게 된다면 값을 선택하지 못하고 넘어갈때도 있기 떄문이다.
그리고 이분탐색의 최대 조건은 N일 에 값들을 다 더한것이여야한다. 그래야 한번 만에 다 선택할수 있을것이다.

그렇게 최소 조건과 최대 조건을 줄이고 늘리면 최적의 값을 찾는 알고리즘을 작성했다.

코드

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

int N,M;
int low=-987654321,high,mid,temp,d,count_T;
int 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 >> d;
        low=max(low,d);
        v.push_back(d);
        high+=d;
    }
    
    while(low<=high) {
        mid=(low+high)/2;
        
//        cout << mid << "\n";
        temp=0;
        count_T=1;
        
        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;
}