[프로그래머스] level 3 - 예산

https://programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산 | 프로그래머스

 본 문제는 정해진 예산 총액 이하에서 가능한 최대의 총예산을 나눠주는 문제다. 문제의 조건으로

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정합니다.

가 있다. 예산을 나눠줄 때 상한선을 두고 상한선 보다 낮게 요청한 지방에는 요구한 예산만큼, 상한선 보다 높게 요청한 지방에는 상한선만큼 나눠줬을 때, 합이 예산 총액 보다 낮아야 한다. 가능한 최대의 총 예산을 나눠줘야 하기 때문에 이분 탐색을 이용하면 쉽게 문제를 해결할 수 있다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int answer = 0;
 
void cal(vector<int> &v, int start, int end, int m) {
    if (start > end) return;
    int mid = (start + end) / 2;
    int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] < mid) {
            sum += v[i];
        }
        else sum += mid;
    }
    if (sum <= m) {
        answer = mid;
        cal(v, mid+1, end, m);
    }
    else {
        cal(v, start, mid-1, m);
    }
}
 
int solution(vector<int> budgets, int M) {
    sort(budgets.rbegin(), budgets.rend());
    cal(budgets, 0, budgets[0], M);
    return answer;
}