프로그래머스 : 예산

풀이1 : 이분탐색

 

최대와 최소를 이용해 mid 를 구하고

mid를 움직여 가면서 최적의 값을 구한다.

---

#include <vector>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

int solution(vector<int> budgets, int dd) {
    long M = dd;
    long sum = 0;
    for(int i=0; i<budgets.size(); i++){
        sum+=budgets[i];
    }
    long min = 0;
    long max = sum;
    long mid = (min+max)/2;
    if(sum <= M){
        return *max_element(budgets.begin(),budgets.end());
    }
    long premid=0;
    while(true){
        sum = 0;
        mid = (max+min)/2;
        if(mid == premid){
            break;
        }
        for(int i=0; i<budgets.size(); i++){
            if(mid > budgets[i]){
                sum+=budgets[i];
            }else{
                sum+=mid;
            }
        }
        if(sum<M){
            min = mid;
        }else if(sum>M){
            max = mid;
        }else{
            return mid;
        }
        premid = mid;
    }

    return premid;
}

---

풀이2

평균보다 낮은거는 예산에서 빼주고

남은 예산의 평균으로 상한가를 구한다.

---

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

int solution(vector<int> budgets, int M) {
    int answer = 0;
    long sum = 0;
    for(int i=0; i<budgets.size(); i++){
        sum += budgets[i];
    }
    if(sum <= M){
        return *max_element(budgets.begin(), budgets.end());
    }
    sort(budgets.begin(), budgets.end());
    int num = budgets.size();
    for(int i=0; i<budgets.size(); i++){
        if(budgets[i]>M/num){
            return M/num;
        }else{
            M-=budgets[i];
            num--;
        }
    }
    return answer;
}

 

 

vector 를 accumulate 로 원소들의 합을 구햇는데

그냥 실행시에는 longlong 값도 잘 나왔는데

테케를 돌리면 안됬었다.