[C++][백준 2512] 예산

[문제]

https://www.acmicpc.net/problem/2512

2512번: 예산

[문제 풀이]

이분 탐색을 이용해서 푸는 문제이다.

지방 예산의 최댓값에서 부터 0까지의 범위에서 얼마를 써야 최대로 쓸 수 있는지 파악하자.

 

지방 예산의 최댓값을 파악하면서 동시에 지방 예산의 최댓값을 모두 합쳤을때보다 예산이 높다면 최댓값을 반환시켜주자. (18~27)

이분 탐색을 이용하자.(33~53)

이분 탐색 도중 예산값을 얼만큼 가져갈 수 있는지 파악하자.(37~44)

[코드]

#include<iostream>
#define endl "\n"
 
using namespace std;
 
int budget[10001];
 
void solve(int n,int m){
 
    int high = 10000;
    int low = 0;
    int mid = 0;
    int answer = 0;
 
    long long total = 0;
 
    int Max = 0;
    for(int i = 0;i<n;i++){
        total += budget[i];
        if(Max<budget[i]){
            Max = budget[i];
        }
    }
    if(total<m){
        cout<<Max<<endl;
        return;
    }
 
    mid = (high + low) / 2;
    high = Max;
 
 
    while(low<=high){
        total = 0;
        mid = (high + low) / 2;
 
        for(int i = 0;i<n;i++){
            if(budget[i]<mid){
                total += budget[i];
            }
            else{
                total += mid;
            }
        }
 
        if(total>m){
            high = mid -1;
        }
        else if(total<=m){
            answer = mid;
            low = mid + 1;
        }
    }
 
    cout<<answer<<endl;
    return;
}
 
int main(){
    int n,m;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>budget[i];
    }
    cin>>m;
    solve(n,m);
    return 0;
}