BOJ 백준 6236 용돈관리 풀이(C++)

문제 링크

이 문제는 흔히 최적화 문제라고 부르는 문제로서 특정 상황이 주어졌을 때 그 상황을 만족하는 최솟값, 최댓값 등의 특정 값을 찾는 문제이다.

처음에 이 문제의 분류는 분할정복 문제로 되어있는데 도대체 어떤 기준으로 문제를 작게 쪼개어야할지 감이 오지 않아 머리만 싸매고 있던 도중

파라메트릭 서치(Parametric Search)라는 접근법이 있다는 것을 알게 되었다. 파라메트릭 서치에 대한 설명은 이 글을 읽으면 어느 정도 감이 올 것이다.

이 알고리즘을 사용하면 위의 문제에서 통장에서 인출해야할 최소 금액을 구하는 문제에서 특정 금액을 인출했을 경우 예산대로 돈을 사용할 수 있는가에 대한 문제로 변환하여 풀 수 있다.

예를 들어 위의 예시에서 탐색 범위를 하루 최소 사용 금액인 100원에서 한 번에 사용한 모든 돈을 꺼냈을 때 경우인 1001원까지라고 해보자. 

1. 100 - 1001까지의 범위일 때 중간값은 550이다. 이 때 5번의 인출로 계획대로 돈을 사용할 수 있는지를 검사한다. 550원을 인출금액으로 했을 경우 5번의 인출로 계획대로 돈을 사용할 수 있다. 그러나 최솟값이라는 보장이 없으므로 값을 저장해두고 원래 범위에서 550미만의 범위만을 가지고 이 과정을 반복한다.

2. 100 ~ 549까지의 범위일 때 중간은 324이다. 인출 금액이 324원일 경우 400원, 500원을 사용할 수 없게 되므로 다시 325원부터 549원까지의 범위를 검사해본다.

3. 위와 같은 과정들을 반복해나가면 범위와 중간값은 아래와 같이 변하게 된다.

 100 - 1001(550) -> 100 - 549(324) -> 325 - 549(437) -> 438 - 549(493) -> 494 - 549(521) -> 494 - 520(507) -> 494 - 506(500) -> 494 - 499(496) -> 497 - 499(498) -> 499 - 499(499) -> 500 - 499(종료)

범위의 대소관계각 바뀌는 순간 탐색이 종료되게 되며 탐색이 종료된 시점에 마지막으로 저장했었던 500이 원하는 최소값이 된다.

접근하기도 어려웠지만 파라메트릭 서치를 사용함으로서 어떠한 값이 특정 조건을 만족하지는지만 검사하면 되는 간소한 문제로 바뀌었다.

이 문제에서 적용해야할 조건은 아래와 같다.

1. 인출 금액이 사용할 금액보다 적지는 않은지 -> 적을 경우 더 큰 범위에서 탐색

2. 인출 금액이 사용할 금액보다는 크지만 현재 소지한 금액은 사용할 금액보다 작은 경우 -> 돈을 인출하고 계속 진행

3. 가진 금액이 소지한 금액보다 많지만 남은 인출횟수와 반복문을 순회할 남은 횟수가 같은 경우 -> 돈을 인출하고 계속 진행

3번의 조건없이 1번과 2번경우만 있을 경우 인출 횟수를 맞추기 위해 돈을 다시 넣고 인출할 수 있다는 조건이 고려되지 않아 오답이 뜨게 된다.

주어진 상황에 대해서 일반적인 최적화 해법을 찾으려고 하면 답을 구하기 어려웠던 문제이다.

이번 문제를 풀기 어려웠던 분들은 최적화 문제를 결정 문제로 바꾸어푸는 위의 접근방식과 파라메트릭 서치에 관한 아이디어를 배워가시면 좋을 거 같다.

아래는 소스코드이다.

#include <cstdio>
using namespace std;
 
int N, sum = 0, answer;
int money[100001];
void check(int m, int start, int end) {
    while(start<=end) {
        int limit = (start+end)/2, mn=0, flag=0;
        int nowMoney = 0;
        for(int i=0; i<N; i++) {
            if(money[i] > limit) {
                flag = 1;
                break;
            }
            if(money[i] > nowMoney) {
                nowMoney = limit;
                mn++;
            }
            else if((m-mn) == (N-i)) {
                nowMoney = limit;
                mn++;
            }
            nowMoney -= money[i];
        }
        if(flag == 1) {
            start = limit+1;
        }
        else if(mn == m) {
            answer = limit;
            end = limit-1;
        }
        else if(mn > m) {
            start = limit+1;
        }
        else {
            end = limit-1;
        }
    }
}
 
int main() {
    int M, minValue=10000;
    scanf("%d %d", &N, &M);
 
    for(int i=0; i<N; i++) {
        scanf(" %d", &money[i]);
        sum += money[i];
        if(money[i]  < minValue) {
            minValue = money[i];
        }
    }
    check(M, minValue, sum+1);
    printf("%d\n", answer);
}