문제

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

풀이

• 배정된 예산들 중 최댓값은 상한액일 수도, 요청한 예산을 모두 줄 수 있어 그중 최댓값일 수도 있다.
• 따라서 요청한 예산의 최솟값 ~ 최댓값 안에 구하고자 하는 값이 있는데, 구하고자 하는 값이 요청한 예산들을 모두 만족하는지 확인해야 한다.
• 완전탐색으로 풀게되면 요청 예산의 수 (지방의 수) N은 3 이상 10,000 이하이므로 최악의 경우 10,000 x 10,000 = 1억이므로 시간초과가 날 수 있다.

따라서 이분 탐색을 통해 범위를 반씩 줄여가며 탐색한다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int arr[100001];
int high, low = 0, ans;

bool isPossible(int mid){
    int sum = 0;

    for(int i=0;i<N;i++){
        if(arr[i] < mid) sum += arr[i];
        else sum += mid;
    }

    if(sum <= M) return true;
    
    return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N;
    for(int i=0;i<N;i++){
        cin >> arr[i];
        high = max(high, arr[i]);
    }
    cin >> M;

    while(low <= high){
        int mid = (low + high)/2;

        if(isPossible(mid)) {
            ans = mid;
            low = mid + 1;
        }
        else high = mid - 1;
    }

    cout << ans << "\n";

    return 0;
}