백준 2512번 - 예산

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

이분탐색 문제로 제법 정답률이 낮은 문제이다.

문제를 해결한 방법은 가장 높은 금액을 high값으로 설정한 뒤에

계속해서 mid를 구해 나가면서 합계가 주어진 M값이 되는지 확인하도록 했다.

high값이 low와 같아지면서 합계가 M값을 만족하지 않을 때

이 합계는 M값보다 큰, 가장 작은 합계가 된다.

즉, high에서 1을 빼준 뒤에 구한 mid값은 M보다 작은 가장 큰 상한값이 된다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N,M;
vector<int> vec;
 
int binarySearch(int low, int high){
    
    int sum=0;
    int mid=(low+high)/2;
    while(high>=low){
        
        sum=0;
        for(int i=0;i<N;i++)
            sum+=(vec[i]>mid)? mid:vec[i];
        
        if(sum==M)
            return mid;
        
        if(sum>M)  high=mid-1;
        else    low=mid+1;
        
        mid=(low+high)/2;
    }
    
    //low=n일 때 mid와 high는 n-1
    return mid;
}
 
int main(){
    
    scanf("%d",&N);
    
    int high=0;
    vec=vector<int> (N,0);
    for(int i=0;i<N;i++){
        scanf("%d",&vec[i]);
        
        if(vec[i]>high)
            high=vec[i];
    }
    
    scanf("%d",&M);
    cout<<binarySearch(0,high)<<endl;
    
    return 0;
}