[프로그래머스] 예산

프로그래머스

이분탐색

 

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

코딩테스트 연습 - 예산 | 프로그래머스

 

 

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int solution(vector<int> budgets, int M) {
    int answer = 0;    
    
    sort(budgets.begin(), budgets.end());
        
    long sum = 0;
    for(int budget: budgets) sum += budget;
        
    if(sum <= M) return budgets[budgets.size()-1];
        
    int max = budgets[budgets.size()-1];
    int min = (int) floor(M / budgets.size());
    int mid = 0;
    int compareMid = 0;
        
    while(true){
     	mid = (int) ceil((max+min) / 2);
       	sum = 0;
        	
       	for(int budget: budgets) sum += ( budget > mid ) ? mid : budget;
        	
    	if(mid == compareMid){
    		answer = mid;
    		break;
    	}
        
        if(sum > M){
        	max = mid;
        } else {
        	min = mid;
        }
        compareMid = mid;
    }
    
    return answer;
}

 

참고

https://jee-goo.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89%EC%98%88%EC%82%B0

[프로그래머스][이분탐색]예산