(C++) - 프로그래머스(Programmers) : 예산 답

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

코딩테스트 연습 - 예산

상한액을 잘 배정해야되는 이분탐색 문제였습니다.

 

풀이방법 : 다음과 같이 두가지의 경우로 나누어 해결했습니다.

1. 상한액을 배정할 필요가 없는 경우 : 즉 총 예산 M보다 budgets에 담긴 전체 예산이 더 적을 경우엔 budgets들 중 가장 큰 값을 반환합니다. 저의 경우 이 부분이 없어 계속 틀렸습니다.

2. 상한액을 이분탐색을 통해 배정해야되는 경우 : 이분탐색을 통해 상한액을 배정한 결과 드는 예상 비용이 M보다 적은 것들 중 최대의 값을 찾습니다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
 
int solution(vector<int> budgets, int M) {
    ll sum = 0, answer = -1;
    ll l = 1, r = M;
    ll sum = 0;
    int m = 0;
    for(auto &i : budgets){sum+= i; m = max(m,i);}
    if(sum <= M) return m; //상한가가 그냥 가장 높은 예산이라면 가장 높은 예산 리턴
    while(l<=r){
        //mid : 상한선
        ll mid = (r+l)/2;
        sum= 0;
        for(int i = 0 ; i < budgets.size(); i++){
            if(mid <= budgets[i]) sum += mid; //넘거나 같으면 그냥 상한가
            else sum += budgets[i]; //넘지 않으면 요청액 그대로 배정         
        }
        //상한가 줄여야
        if(sum > M) r = mid-1;
        //상한가 늘려야
        else if(sum <= M){l = mid+1; answer = max(answer,mid);}
    }
    return answer;
}