6236번_용돈 관리_BOJ

문제 링크

6236번 용돈 관리 : https://www.acmicpc.net/problem/6236

문제 설명 및 해결 아이디어

Parametric Search문제이다.

left의 범위는 이용할 금액중 가장 큰 값부터 시작하면 된다.

mid는 인출 할 금액 K로 설정한다.

특정 mid값으로 인출한 횟수가 주어진 M보다  클 경우, mid값을 크게하여 인출 횟수를 줄인다.

반대의 경우, mid값을 작게하여 인출 횟수를 늘릴 수 있다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long int
 
ll n, m, num, res, maxv;
vector<ll> spend;
 
ll isPossible(ll withdraw) {
    ll cnt = 1;
    ll passbook = withdraw;
    for (int i = 0; i < n; ++i) {
        if (passbook - spend[i] >= 0) {
            passbook -= spend[i];
        }
        else {
            cnt++;
            passbook = withdraw - spend[i];
        }
    }
    return cnt;
}
 
ll func() {
    ll left = maxv, right = 1000000000;
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (isPossible(mid) > m)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return left;
}
 
int main() {
    scanf("%lld %lld", &n, &m);
    maxv = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &num);
        spend.push_back(num);
        maxv = max(maxv, num);
    }
    res = 0;
    printf("%lld\n", func());
    return 0;
}