[백준 2512번] 예산 (C++)

문제링크 : https://www.acmicpc.net/problem/2512

2512번: 예산

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int arr[10001];

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    sort(arr, arr+N);

    int l = 0, r = arr[N-1];
    int sum, result = 0;

    while(l<=r)
    {
        sum = 0;
        int mid = (l+r)/2; //상한액
        for(int i=0; i<N; i++)
        {
            sum += min(arr[i], mid);
        }
        
        if(M>=sum)
        {
            result = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }

    cout << result;
    
    return 0;
}

이분탐색을 이용하여 푸는 문제다.

상한액을 mid 값으로 설정하고, 기존 배열과 비교하여 둘 중 작은 값을 더해나간다.

이렇게 더해나간 값이 총 예산 값인 M보다 작거나 같다면 해당 mid 값은 정답의 기준에 맞는 것이므로 result에 저장한다.

하지만 더 나은 정답이 있을 수 있으므로 탐색은 계속하여 최적의 mid 값을 찾는다.