[프로그래머스] 예산

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

이 문제는 이분탐색을 통해 해결할 수 있다. 이분 탐색을 위한 left와 right를 설정해야하는데 left는 0, right는 budgets의 최댓값으로 시작하여 이분탐색을 하여 상환액을 결정하면 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;
    int left = 0;
    //
    int right = *max_element(budgets.begin(), budgets.end());
    int sum = 0;
    while (left <= right) {
        int mid = (left + right) / 2;
        sum = 0;
        for (int v : budgets){
            if (v < mid) sum += v;
            else sum += mid;
        }
        if (sum > M) {
            right = mid - 1;
        }
        else {
            answer = max(answer, mid);
            left = mid + 1;
        }
    }
    return answer;
}