백준 2512번: 예산 C++코드(이진 탐색)

#include<iostream>

using namespace std;

int values[10001];

int search(int n,int m, int standard){
    int result = 0;
    for(int i=0; i<n; i++){
        if(values[i] <= standard){
            result += values[i];
        }else{
            result += standard;
        }
    }
    if(result <= m){
        return 1;
    }else{
        return 0;
    }
}

int binarysearch(int max, int n, int m){
    int low = 0, high = max;
    int standard = 0;
    int result = 0;
    while(low <= high){
        //cout << low << " " << high << endl;
        standard = (high+low)/2;
        if(search(n,m,standard) == 1){
            result = standard;
            low = standard+1;
        }else{
            high = standard-1;
        }
    }
    return result;
}

int main(){
    int n, m;
    int max = 0;
    cin >> n;
    int sum = 0;
    for(int i=0; i<n; i++){
        cin >> values[i];
        if(values[i] > max){ max = values[i]; }
        sum += values[i];
    }
    cin >> m;
    if(sum <= m){
        cout << max;
    }else{
        cout << binarysearch(max, n, m);    
    }
}

설명

이분 탐색을 이용해서 푸는 문제이다.  예산요청액 중 가장 큰 값(high)과 0(low)의 중간값을 상한액으로 잡고 상한액을 다 더했을 때(상한액보다 예산요척액이 적을 경우 예상요청액을 더한다), 총 예산보다 적으면 low를 중간값으로 바꿔주고 다시 이분탐색을 진행하는 식으로 하면 된다.

 

문제점

만약 127과 128이 low와 high일경우 중간값이 계속 127로 걸려서 무한루프가 생기기도 했다. 이는 low는 중간값+1 high는 중간값-1로 해결해주었다.