[C++] 백준 2512 : 예산

백준 2512 : 예산

 

문제 링크

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

2512번: 예산

 

 

문제 내용

국가의 역할 중 하나는 여러 지방의 예산 요청을 심사하여 국가의 예산을 분배하는 것이다. 국가예산의 총액은 미리 정해져 있어서 모든 예산 요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정한다.

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산 요청에는 모두 상한액을 배정한다. 상한액 이하의 예산 요청에 대해서는 요청한 금액을 그대로 배정한다. 

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 하자. 이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 된다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성하시오.

 

 

Idea

이분탐색을 통해 상한액을 계산해야 하는 문제였다.

 

그러나 단순히 이분탐색을 통하여 while문을 탈출했을 때의 값을 출력하면 이상이 생길 수 있으므로, 임의의 상한액으로 인한 총합이 m보다 작거나 같을 때 해당 상한액을 다른 변수에 저장시켜주어야 한다.(line 51)

 

여기서 사용한 이분탐색의 조건으로는 임의의 상한액으로 인한 예산 총합을 기준으로 나누는데 이때 예산 총합을 구할 때에도 이분 탐색을 사용하였다. (line 37 ~ line 43)

단순히 인덱스 0부터 순환하여 더해줄 수도 있지만 이분탐색을 통해 추출한 인덱스로 보다 빠르게 합계를 계산하는 데 사용하였다.

 

그리고 모든 경우에 이분탐색을 진행하는 것이 아니라 요청한 예산의 총합이 m보다 클 때에만 적용한다. 만약 작다면 상한액은 요청된 예산들 중 최댓값이다. (line 25 ~ line 26)

 

(사실 아래 코드에서 result를 초기화 시켜주는걸 깜박.... 했지만 고치기 귀찮...)

 

 

Code

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
int main()
{
    int n, m, total = 0, money;
    vector<int> v;
 
    // input
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &money);
        total += money;
        v.push_back(money);
    }
    scanf("%d", &m);
 
    // sort
    sort(v.begin(), v.end());
 
    // solution
    if (total < m)
        printf("%d\n", v[n - 1]);
    else
    {
        int left = 0;
        int right = v[n - 1];
        int result;
 
        // binary search
        while (left <= right)
        {
            int mid = (left + right) / 2;
            int idx = lower_bound(v.begin(), v.end(), mid) - v.begin();
            
            // budget calculation
            int sum = 0;
            for (int i = 0; i < idx; i++)
                sum += v[i];
            sum += (mid * (n - idx));
 
            // binary search role
            if (sum > m)
                right = mid - 1;
            else
            {
                left = mid + 1;
                result = mid;
            }
        }
 
        // result
        printf("%d\n", result);
    }
    return (0);
}