[프로그래머스] 예산

[프로그래머스] 예산

문제 링크

#include "header.h"
#define MAX 1000000001
using namespace std;
long long check(vector<int> & budgets, int mid){
    // mid = 상한선!
    long long total = 0;
    for(int i=0; i<budgets.size(); i++){
        if(mid >= budgets[i]){
            total += budgets[i];
        }else{
            total += mid;
        }
    }

    return total;
}
int solution(vector<int> budgets, int M) {
    int answer = 0;

    int left = 0;
    long long right = M;

    while(left <= right){
        int mid = left + (right - left) / 2; //상한액
        long long ret = check(budgets, mid);

        if(ret > M){ //예산 초과
            right = mid - 1;
        }else{
            left = mid + 1;
            answer = max(answer, mid);
        }
    }
    
    if(answer == M){
        long long ret = 0;
        for(long long cur : budgets) ret = max(ret, cur);
        return ret;
    }
    return answer;
}

• 간단한 이분탐색 문제. 일단 범위가 1억이 넘으면 이분탐색 접근법을 생각 해 보는게 좋을 것 같다.
• mid를 선언 할 때, 오버플로우를 막기 위해 left + (right - left) / 2를 해 주었다.
• mid를 상한선으로 잡고, 해당 상한선으로 얼마만큼의 예산이 소비되는지 check함수를 통해 계산한다.
• 만약 예산이 초과된다면, 상한선을 줄인다.
• 예산이 초과가 되지 않았으면, 상한선을 올리고, 답을 업데이트 한다.
• 문제가 조금 불친절한 감이 있는데, 만약 [1, 1, 1, 1], 400 같이 모든 요청이 배정될 수 있다면 1+1+1+1 을 반환해야 한다.
• 효율성에서 문제가 발생하면 budgets을 더하는 인자를 long long으로 바꿔야 한다. (1억이 넘으므로 int 범위 벗어남)