백준 6236 용돈관리

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

#include <iostream>
#include <vector>


using namespace std;

vector<int> arr;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;

    cin >> n >> m;

    arr.resize(n);

    int s = 0;
    int mn = 0;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        s += arr[i];
        mn = max(mn, arr[i]);
    }

    int l = mn;
    int r = s;
    int ans = s;

    while (l <= r) {

        //하루에 뺄 금액 k
        int mid = (l + r) / 2;

        //당일 사용하고 남은 금액
        int sum = mid;
        //인출 횟수
        int cnt = 1;
        for (int i = 0; i < n; i++) {
            if (sum - arr[i] < 0) {
                cnt++;
                sum = mid - arr[i];
            } else {
                sum -= arr[i];
            }
        }

        if (cnt <= m) {
            ans = min(ans, mid);
            r = mid - 1;
        } else {
            l = mid + 1;
        }



    }

    cout << ans;


    return 0;
}

 

 문제

n일 동안 m번 통장에서 돈을 인출하여 사용할 건데, 그날그날 사용할 금액을 정해놓았고, 인출은 k원의 금액을 m번 인출할 예정이다. 이때 k의 최솟값을 구하라.

풀이

 이분탐색 문제이다. k를 구하는 것이므로 k에 들어갈 값을 mid로 잡고 연산을 수행한다.

 //하루에 뺄 금액 k
        int mid = (l + r) / 2;

        //당일 사용하고 남은 금액
        int sum = mid;
        //인출 횟수
        int cnt = 1;
        for (int i = 0; i < n; i++) {
            if (sum - arr[i] < 0) {
                cnt++;
                sum = mid - arr[i];
            } else {
                sum -= arr[i];
            }
        }

 첫 날 금액을 인출하고, 금액을 인출한 횟수(cnt)를 1로 잡는다. 그 후 각 날에 대하여 그날 사용할 금액만큼(arr[i]) sum에서 차감한다.

 당일 예산이 현재 가지고 있는 금액보다 클 경우에는 금액을 새로 뽑아야 하므로 cnt를 증가하고, sum은 새로 뽑은 금액(mid)에서 그 날 예산을 차감한다. 그렇지 않을 경우에는 가지고 있는 돈에서 해당 예산만큼 차감하면 된다.

        if (cnt <= m) {
            ans = min(ans, mid);
            r = mid - 1;
        } else {
            l = mid + 1;
        }

  m번보다 적거나 같게 사용했을 경우 사용 금액을 줄여야 인출 횟수가 늘어나므로 mid보다 작은 범위에 대해 이분탐색을 수행한다. 만약 같다 하더라도 k는 최솟값이어야 하므로 계속 탐색한다. 반대의 경우에는 mid보다 큰 범위에 대해 이분탐색을 수행한다. 

 수행하여 나온 결과를 출력하면 정답을 구할 수 있다.