[백준] 6236 용돈 관리

6236번: 용돈 관리

 

www.acmicpc.net

풀이

이분 탐색으로 해결할 수 있는 문제이다. K금액을 기준으로 이분 탐색을 진행하면 된다. 이 때 left는 1원부터 인출 가능하므로 1, right는 전체 금액을 한번에 인출할 수 있기 때문에 전체 금액이 된다.

코드

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

int n, m;
int money[100001];

bool is_possible(int mid) {
    int cnt = 1;
    int sum = mid;

    for (int i = 0; i < n; i++) {
        // 돈을 인출해도 그 날 사용 금액보다 적으면 false
        if (mid < money[i]) return false; 

        // 남은 돈이 그 날 사용 금액보다 적은 경우
        if (sum - money[i] < 0) {
            sum = mid; // 남은 돈을 통장에 넣고 mid만큼 인출
            cnt++;
        }
        sum -= money[i];
    }
    return cnt <= m;
}

int binary_search(int r) {
    int left = 1;
    int right = r;
    int ans = 987654321;

    while (left <= right) {
        int mid = (left + right) / 2;        

        if (is_possible(mid)) {
            right = mid - 1;
            ans = min(ans, mid);
        }
        else {
            left = mid + 1;
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> money[i];
        sum += money[i];
    }

    cout << binary_search(sum) << '\n';
    return 0;
}