[백준] 2512 : 예산

www.acmicpc.net/problem/2512

2512번: 예산

---

• 예산들에 대해서 임의의 상한값을 잡고 매번 검사해야 하는데, 상한값의 범위가 크기 때문에 반씩 잘라서 유효성을 검사한다.
• 이분 탐색을 시작할 때 high 값은 예산들의 최댓값을 검사해도 되지만, low 값을 예산들의 최솟값으로 두고 검사할 경우 전체 예산의 상한액에 따라서 애초에 불가능할 수 있기 때문에 low 값을 0 부터 시작하는 것이 맞다.
• 어차피 상한값은 배열의 인덱싱과 상관없기 때문에, 배열 자체를 정렬할 필요는 없고 최댓값만 알고 있으면 된다.

---

#include <iostream>
#include <algorithm>

using namespace std;

int n;
int bud[10000];
unsigned long long m, answer;

int main(void)
{
    cin >> n;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> bud[i];
        answer += bud[i];
    }
    cin >> m;
    sort(bud, bud + n);                 // 예산들 정렬
    if(answer <= m)                     // 모든 요청이 배정될 수 있는 경우에는
    {
        cout << bud[n-1] << endl;       // 요청한 금액 그대로 배정하고 최대예산 출력
        return 0;
    }

    int low = 0, high = bud[n-1];       // 최솟값은 0, 최댓값은 최대예산으로 시작
                                        // 최솟값을 최소예산으로 시작할 경우 논리적 오류 발생 가능
    while(low <= high)
    {
        int mid = (low + high) / 2;     // mid 를 상한액으로 잡고
        unsigned long long total = 0;
        for(int i = 0 ; i < n ; i++)    // 예산을 집행했을 때
        {
            if(bud[i] < mid) total += bud[i];
            else total += mid;
        }
        if(total <= m)                  // 집행이 가능한 경우라면
        {
            answer = mid;               // 답을 갱신시켜주고
            low = mid + 1;              // 위쪽 이분탐색 실시
        }
        else                            // 불가능한 경우라면
        {
            high = mid - 1;             // 아래쪽 이분탐색 실시
        }
    }

    cout << answer << endl;
}