[ 프로그래머스 예산 (Lv3) ] (C++)

프로그래머스의 예산(Lv3) 문제이다.

[ 문제풀이 ]

주어진 총액 이하에서 배정할 수 있는 최대 예산을 구해야 하는 문제이다.

본인은 이분탐색을 이용해서 이 문제에 접근해 보았다.

먼저, 상한액으로 설정할 수 있는 최대액수를 구하기 위해서 각 나라별로 요청한 예산액 중 가장 큰 액수를 상한액의 최대값으로 설정해 주었다. 또한, 시작액은 0원으로 설정해서 이분탐색을 진행해 주었다.

탐색은 "현재 설정한 상한액" 으로 각 나라에 금액을 배정했을 때, 그 총 합이 전체 국가예산의 값을 넘는지 안넘는지를 판단해 주었다.

[ 소스코드 ]

#include <vector>
 
using namespace std;
 
int Max(int A, int B) { if (A > B) return A; return B; }
 
long long Binary_Search(int Mid, vector<int> B)
{
    long long Result = 0;
    for(int i = 0 ; i < B.size(); i++)
    { 
        if (B[i] > Mid) Result = Result + Mid;
        else Result = Result + B[i];
    }
    return Result;
}
 
int solution(vector<int> budgets, int M) 
{
    int answer = 0;
    int Start = 0;
    int End = 0;
 
    for (int i = 0; i < budgets.size(); i++)
    {
        if (budgets[i] > End) End = budgets[i];
    }
    
    while (Start <= End)
    {
        int Mid = (Start + End) / 2;
        if (Binary_Search(Mid, budgets) > M) End = Mid - 1;
        else
        {
            answer = Max(answer, Mid);
            Start = Mid + 1;
        }
    }
    return answer;
}