6236번 용돈 관리

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

이분 탐색 ps 파라메트릭 서치 이진 탐색 복습 코딩 코테 추천 필수 생각 문제 이해

처음에 문제를 잘 이해하지 못 했다.

문제에서 요구하는 것(정답)은 무조건 통장에서 K원만 인출한다.

그리고, 그 K원을 가지고 입력으로 주어지는 하루에 사용할 금액과 비교한다.

그렇게 계속 계속 사용하다가 어느 순간 돈이 모자를 때에는 남은 돈(내 코드에서의 money)은 무시하고,

다시 K원을 인출한다. 인출할 때마다 인출 횟수(cnt)를 1 증가시킨다.

#include<bits/stdc++.h>
 
using namespace std;
 
int n, m;
vector<int> v;
 
bool chk(int mid) 
{    
    int cnt = 0, money = 0;
 
    for (auto i : v) {
        if (i > mid) {
            return false;
        }
 
        if (money - i < 0) {
            money = mid;
            ++cnt;
        }
        
        money -= i;
    }
 
    return cnt <= m;
}
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d %d", &n, &m);
 
    int Left = 1, Right = 0, answer = 1e9;
 
    v.assign(n, 0);
    for (int i = 0; i < n; i++) {
        scanf("%d", &v[i]);
        Right += v[i];
    }
 
    while (Left <= Right)
    {
        int mid = (Left + Right) >> 1;
 
        if (chk(mid)) {
            Right = mid - 1;
            answer = min(answer, mid);
        }
        else {
            Left = mid + 1;
        }
    }
 
    printf("%d\n", answer);
 
    return 0;
}