[백준/C++] 6236번 : 용돈관리

 

 

풀이

• 최소 금액 K의 범위를 생각해봅시다. K는 각 날짜마다 필요한 금액보다는 크거나 같아야 합니다. 즉, K는 1부터 N * 최대 사용 금액 사이의 값일 수 있다.
• 이분 탐색을 이용하여 가능한 K 값을 찾습니다. 이때, 이분 탐색의 중간값(mid)을 사용하여 K를 검사한다.
• 주어진 N일 동안 각 날짜별로 사용할 금액을 순회하면서 현재 인출 가능한 금액(mid)로 사용할 수 있는지 확인한다.
• 만약 mid로 사용할 수 없는 날이 나온다면, 인출 횟수를 늘려야한다.
• 만약 인출 횟수가 M 이하라면, 가능한 K값 중 작은 범위에서 다시 탐색. 그렇지 않다면, K값을 더 큰 범위에서 탐색한다.
• 위를 반복하여 최소금액 K를 찾으면 된다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> dailyExpenses(N);
    int maxExpense = 0; 

    for (int i = 0; i < N; ++i) {
        cin >> dailyExpenses[i];
        maxExpense = max(maxExpense, dailyExpenses[i]);
    }

    int left = maxExpense;  
    int right = N * maxExpense;  
    int answer = right;  

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

        for (int expense : dailyExpenses) {
            if (total < expense) {
                // 남은 금액으로 사용 불가능한 경우
                count++;
                total = mid;  // 다시 K원 인출
            }
            total -= expense;
        }

        if (count <= M) {
            answer = min(answer, mid);
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << answer << endl;

    return 0;
}

 

 

 

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

6236번: 용돈 관리