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

문제 링크: programmers.co.kr/learn/courses/30/lessons/43237

코딩테스트 연습 - 예산

1. 주의할 점

- 이분탐색을 통해 접근하며, 입력 받는 벡터를 미리 Sort 하면 편하다

 

2. 구현

- 입력 받는 벡터를 Sort한 후, 이분탐색을 통해 상한액을 Mid만큼으로 잡았을 때, M 이하의 예산으로 배분 가능하면 Mid를 늘리고, 아니라면 Mid를 줄이면서 Mid를 구한다

- Mid로 배분이 가능할때마다 Answer의 값을 Mid로 갱신한다

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> v;

bool cal(int mid, int M){
    long long temp=0;
    for(int i=0;i<v.size();i++){
        if(v[i]<=mid)  temp+=v[i];
        else{
            temp+=(mid*(v.size()-i));
            break;
        }
    }
    if(temp<=M) return true;
    return false;
}

int solution(vector<int> budgets, int M) {
    int answer = 0;
    v = budgets;
    sort(v.begin(),v.end());
    
    long long l=0,r=v[v.size()-1],mid;
    while(l<=r){
        mid = l+(r-l)/2;        //상한액
        if(cal(mid,M)){
            answer=mid;
            l=mid+1;
        }
        else
            r=mid-1;
    }
    return answer;
}