백준 2512 <예산> C++ 풀이

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

2512번: 예산

문제

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

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

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

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

입력

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. 

출력

첫째 줄에는 배정된 예산들 중 최댓값인 정수를 출력한다. 

 

 

 

# 풀이

 

상한액을 정할 기준을 잡는게 문제의 첫번째 포인트였습니다. 저는 처음에는 예산총액을 절반으로 나눈 평균값으로 시작했는데, 이렇게 되면 이분탐색을 진행할 때 right가 총액으로 잡혀있는 바람에 여유있는 상황에서는 오답을 내놓게 됩니다. 그래서 다시 잡아야겠다고 생각하고 문제를 보니, 지방들의 예산 중 최대값을 right로 잡으면 된다는 것을 알았습니다. 그 이상을 배정할 일이 없기 때문이죠.

 

이렇게 되면 left = 0 , right = 예산 중 최댓값 으로 이분탐색이 진행됩니다. 지원해줄 수 있는 최대금액을 기준으로 각 지방의 예산들의 합이 총액을 넘으면 지원 최대금액을 줄이고, 넘지 않으면 늘리는 형식으로 진행해주면 됩니다. 그렇게 되면 제 기존 코드 기준으로 또 한번 문제가 발생했는데, 예제 1처럼 127이 최대이지만 예산을 넘지 않기 때문에 탐색이 한번더 진행되고 128이 기준 최대 금액으로 끝이납니다( while문의 종료조건이 left <= right 이기때문에).

 

이 부분을 해결하기 위해 sub 벡터를 하나 생성합니다. 분기문에서 총액을 sum이 넘기면 그 금액은 채택될수 없기 때문에 sum을 안넘기는 경우와 딱 맞아 떨어지는 경우에 sub에 기준 금액을 push합니다. 그리고 마지막에 sort이후 최댓값을 출력하면 정답이 나오게됩니다! 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
// 1. 정수 상한액정하기
 
int budget[10001];
 
bool cmp(int a, int b)
{
    return a > b;
}
 
int main()
{
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; i++)
    {
        cin >> budget[i];
    }
    sort(budget, budget + N + 1);
    
    int total;
    cin >> total;
 
    int start = 0;
    int left = 0;
    int right = budget[N];
    vector<int> sub;
 
    while (left <= right)
    {
        start = (left + right) / 2;
        int sum = 0;
        for (int i = 1; i <= N; i++)
        {
            if (budget[i] >= start)
            {
                sum += start;
            }
            else
                sum += budget[i];
        }
 
        
        if (sum > total)
        {
            right = start - 1;
        }
        else if (sum < total)
        {
            left = start + 1;
            sub.push_back(start);
        }
        else
        {
            sub.push_back(start);
            break;
        }
    }
 
    sort(sub.begin(), sub.end(), cmp);
    
 
    cout << sub[0];
}