[이분탐색] BOJ 2512: 예산

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

 

예산 내에서 지자체가 요구한 예산들 다 커버할 수 있으면 지자체 중 요구한 예산이 가장 큰 지자체의 예산을, 그렇지 않으면 특정 상한선을 정해서 그 위로는 자르고, 전체 예산안을 만족할 수 있는 상한선 중 가장 큰 값을 반환하면 된다.

 

전자는 그냥 전체 요구 예산의 합이 예산 한도보다 낮으면 최대값을 반환하면 될 것이고, 후자 쪽이 binary search를 통해 상한선의 최대값을 찾아야 하는 문제이다.

 

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

using namespace std;

int answer;

void findMaximum(vector<int> &budget, int min, int max, int maxBudget)
{
    if(min>max) return;
    int medium = (min+max)/2;
    int sum = 0;
    for(int i=0;i<budget.size();i++)
    {
        if(budget[i]>=medium) sum+=medium;
        else sum+=budget[i];
    }

    if(sum<maxBudget)
    {
        answer = medium;
        findMaximum(budget, medium+1, max, maxBudget);
    }
    else if(sum==maxBudget)
    {
        answer = medium;
        return;
    }
    else
    {
        findMaximum(budget, min, medium-1, maxBudget);
    }
}

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

    int N;
    cin>>N;

    vector<int> budget;
    int input;
    int budgetSum = 0;
    int maxBudget = 0;
    for(int i=0;i<N;i++)
    {
        cin>>input;
        budget.push_back(input);
        budgetSum+=input;
        maxBudget = input>maxBudget?input:maxBudget;
    }    

    int totalBudget;
    cin>>totalBudget;

    if(totalBudget>=budgetSum)
    {
        cout<<maxBudget;
        return 0;
    }

    sort(budget.begin(), budget.end());

    findMaximum(budget, 1, maxBudget, totalBudget);
    cout<<answer;
}

 

이 문제에서 삐끗한 함정이 두 가지가 있는데 포스팅에서 짚고 넘어가려 한다.

 

1. binary search의 시작 지점

    sort(budget.begin(), budget.end());

    findMaximum(budget, 1, maxBudget, totalBudget);

 

여기서 예산안을 담은 vector를 오름차순 정렬한 후 binary search를 시작할 때, min 값을 budget의 최소값으로 하면 안 된다. 요구할 수 있는 예산의 최소값인 1부터 시작해야 한다. 가장 작은 예산 요구안조차 상한선을 두고 잘라내는 경우가 생길 수 있기 때문이다.

 

2. binary search 탈출 조건

void findMaximum(vector<int> &budget, int min, int max, int maxBudget)
{
    if(min>max) return;
    int medium = (min+max)/2;
    int sum = 0;
    for(int i=0;i<budget.size();i++)
    {
        if(budget[i]>=medium) sum+=medium;
        else sum+=budget[i];
    }

    if(sum<maxBudget)
    {
        answer = medium;
        findMaximum(budget, medium+1, max, maxBudget);
    }
    else if(sum==maxBudget)
    {
        answer = medium;
        return;
    }
    else
    {
        findMaximum(budget, min, medium-1, maxBudget);
    }
}

 

여기서 처음에 탈출 조건을 min>=max로 설정했는데 이렇게 하면 다음 예시에 걸린다.

5

100 100 100 100 100

10

 

이 input에 대한 정답은 각 지자체에 2씩 배분해 주는 것이지만 min>=max로 탈출 조건을 설정하면 답이 1이 나온다. min=max=medium인 경우도 고려해야 함을 생각하자.