용돈관리 (boj 6236)

용돈관리 문제는 Parametric search 문제에요

Parametric search 는 Binary search 의 아이디어를 가져온 기법입니다.

지금 문제가 최소한의 K원을 찾는 문제니까 최대값은 N * 10000(일일 최대 사용금액), 최소값은 입력받은 일일금액 중 가장 큰 금액일거에요. 예를 들면 N이 100000, M이 1, 그리고 모든 일일금액이 10000원이라면 100000 * 10000 원을 한 번만 뽑아야하겠죠? 이는 100억이라서 int 의 범위를 넘어섭니다. 이를 먼저 주의해야하구요

최소값이 일일금액 중 가장 큰 금액이여야함은 자명하죠? 만약 K보다 큰 일일금액이 있다면 돈이 부족해서 은행에 돈을 넣었다가 다시 뽑아도 돈이 모자르니까요!

 

Max = 100만

Min = 일일금액 중 가장 큰 금액

이렇게 Min, Max 를 구했다면 여기서 Binary search를 하는거에요

 

f(k) = k원으로 M번만에 N일을 살 수 있는가?   살 수 있으면 1 리턴 아니면 0 리턴

중간값 = [Max, Min] / 2

f(중간값) 이 만약 1이라면 k 를 더 낮은 값으로 설정할 수 있다는 것입니다.

따라서 max = 중간값 으로 놓고 다시 새로운 중간값을 구하여 반복합니다.

 

반대로 f(중간값) 이 만약 0이라면 k 를 더 높은 값으로 설정해야 한다는 것입니다.

min = 중간값 + 1으로 놓고 다시 새로운 중간값을 구하여 반복합니다.

 

이 과정을 Min과 Max 가 같아질 때까지 반복하고, 그때의 Max 값이 최소의 K원이 됩니다.

 

 

코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

#define INF 987654321

int N, M;
int arr[100010];
long long max = 1000000000;
long long min = 0;

int parametricSearch(long long k) {
    long long v = k;
    int m = 1;

    for (int n = 0; n < N; n++) {
        if (v >= arr[n]) {
            v -= arr[n];
        } else {
            v = k;
            m++;
            v -= arr[n];
        }
    }

    return m <= M;
}

int main() {
    scanf("%d %d", &N, &M);

    for (int n = 0; n < N; n++) {
        scanf("%d", arr + n);
        min = std::max(min, (long long) arr[n]);
    }

    while (max != min) {
        long long v = min + (max - min) / 2;
        if (parametricSearch(v)) {
            max = v;
        } else {
            min = v + 1;
        }
    }

    printf("%lld", max);
    return 0;
}