BOJ - 2512 ) 예산

---

N개의 지방에게 알맞는 예산을 분배하는 문제이다. 

입력의 마지막에 돈이 주어지는데, 각자 원하는금액을 최대한 맞추어주면서,

내가가지고있는 금액 한도에서 분배해야한다.

 

즉, 요청값을 정렬한 후에 이분탐색으로 적절한 예산을 찾아주면된다.

 

두가지의 예외가 존재하는데,

 

1. 예산이 너무 많아서 모두 원하는만큼 주어도 되는경우

2. 예산이 너무 적어서 원하는금액중 가장 작은 금액으로도 못주는경우

 

만 이분탐색 전에 체크해주면된다.

 

---

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N,Budget,mid,res;
vector < int > want;
void input(){
    cin >> N;
    for(int index = 1 ; index <= N ; index ++){
        int t; cin>> t;
        want.push_back(t);
    }
    cin >> Budget;
}
 
int main(int argc, char** argv) {
    input(); 
 
    sort(want.begin() , want.end());
 
    if(want[N-1]*N <= Budget){
        /// 예산이 너무 많은경우
    cout<< want[N-1];
        return 0;
    }
 
    else if(want[0]*N > Budget){
    /// 예산이 너무 적은경우 
      cout << Budget/N;
        return 0;
    }
 
    else{
 
        int left = want[0] , right = want[N-1];
        while(left <= right){
            
             mid = (left + right) / 2 ;
            int total =0;
            for(int index =0 ; index < N ; index++){
                if(want[index] >= mid){
                    total += mid;
                }
                else total += want[index];
            }
            
            if( total > Budget){
                right = mid -1;
            }
            else {
                res = max(res,mid);
                left = mid +1;
            }
            
        }
    }
    cout << res;
    return 0;
}

---