[C++] 백준 6236 - 용돈관리

문제

현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 하였다. 현우는 통장에서 K원을 인출하며, 통장에서 뺀 돈으로 하루를 보낼 수 있으면 그대로 사용하고, 모자라게 되면 남은 금액은 통장에 집어넣고 다시 K원을 인출한다. 다만 현우는 M이라는 숫자를 좋아하기 때문에, 정확히 M번을 맞추기 위해서 남은 금액이 그날 사용할 금액보다 많더라도 남은 금액은 통장에 집어넣고 다시 K원을 인출할 수 있다. 현우는 돈을 아끼기 위해 인출 금액 K를 최소화하기로 하였다. 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오.

입력

1번째 줄에는 N과 M이 공백으로 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ N)

2번째 줄부터 총 N개의 줄에는 현우가 i번째 날에 이용할 금액이 주어진다. (1 ≤ 금액 ≤ 10000)

출력

첫 번째 줄에 현우가 통장에서 인출해야 할 최소 금액 K를 출력한다.

풀이

K의 최소값을 구하는 문제입니다. 우선 인출 금액이 주어졌을 때 몇번 인출해야 하는지를 구해야 합니다. 해당하는 함수는

1. 최초 1회 인출, 잔돈 = 인출 금액
2. 예산을 사용
3. 예산이 1회 인출 금액보다 크면 불가능
4. 예산이 잔돈보다 크면 새로 인출
5. 예산 사용

이런 구조를 가질 수 있습니다. 위 코드를 작성해보면

bool check(int out) {
    int count = 1;
    int remains = out;
    for (int i = 0; i < n; i++) {
        if (budget[i] > out) return false;
        if (budget[i] > remains) {
            count++;
            remains = out;
        }
        remains -= budget[i];
    }
    return count <= m;
}

이제 main 함수에서 입력을 받고 위 함수가 false에서 true로 바뀌는 경계값을 찾으면 됩니다. 브루트 포스로 하기엔 너무 많은 시간이 걸립니다.
그 이유는, 해당 인출 금액의 범위는 0원에서 예산을 모두 다 더한 값 사이의 수 입니다. 문제에서 주어진 조건을 보면 N과 M은 100,000 까지 가능하므로 최악의 경우 100,000 * 100,000 케이스를 모두 탐색해야 하므로 적절하지 않습니다.
이를 위해 이분탐색을 이용하여 경계값을 찾아야 합니다.

코드

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


int n, m;
vector<int> budget;

bool check(int out) {
    int count = 1;
    int remains = out;
    for (int i = 0; i < n; i++) {
        if (budget[i] > out) return false;
        if (budget[i] > remains) {
            count++;
            remains = out;
        }
        remains -= budget[i];
    }
    return count <= m;
}

int main(void) {
    cin >> n >> m;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        budget.push_back(input);
        sum += input;
    }

    int left = 0;
    int right = sum;
    int count = right;
    while(left <= right) {
        int mid = (left + right) / 2;
        if (check(mid)) {
            right = mid - 1;
            if (count > mid) count = mid;
        }
        else left = mid + 1;
    }
    cout << count << endl;

    return 0;
}