2512 예산

이분탐색 드디어 익숙해졌다!! 랜선 문제는 떠듬떠듬 풀었는데 이건 좀 쉬웠음. 그래서 코드 다 지우고 처음부터 짰다.

 

먼저 범위

범위의 최솟값은 1로 잡았다. 문제 보면 M은 N 이상 1,000,000,000 이하이다. N이상이라고 해서 최솟값이 1이고 두고, 최댓값은 예산의 최댓값 +1 로 뒀다. 

 

그리고 만족하는지 불만족하는지는 설정한 예산 기준으로 작으면 그대로 크면 기준으로 설정했다. 코드로는 min(v[i], mid)으로 짜면 된다. 

 

나머지는 이전이랑 똑같다. 기준을 만족하면 만족하는 최댓값을 늘려주고 만족하지 않는다면 만족하지 않는 최솟값을 줄여준다. 암튼 좀 익숙해진 것 같아서 뿌듯하다. ~.~

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool check(vector<int> v, int mid, int money){
    i64 sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += min(v[i], mid);
    
    if(sum <= money)
        return true;
    else
        return false;
}

int main(){
    int n, m;
    scanf("%d", &n);
    vector<int> v(n);
    
    for(int i = 0; i < n; i++)
        scanf("%d", &v[i]);
    scanf("%d", &m);

    int low = 1;
    int high = *max_element(v.begin(), v.end()) + 1;
    
    while(true){
        if(low == high -1)
            break;
            
        int mid = (low+high)/2;
        if(check(v, mid, m))
            low = mid;
        else
            high = mid;
    }
    
    printf("%d", low);
    return 0;
}