BOJ 2512 - 예산

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

 

2분 탐색으로 풀었다.

오랜만에 2분탐색 문제를 풀어서 재밌었다.

주의할 점은 출력을 '배정된 예산들 중 최댓값인 정수를 출력한다.' 는 것이다.

 

총 예산이 400이고, 지원요청이 100, 80, 95로 이 안에서 모든 예산을 지원할 수 있다고하자.

이 때, 상한선을 130으로 해도 모두 지원가능한데, 어차피 최대 100만 지원하면 되므로 배정된 예산들 중 최대값인 정수는 100이 되고, 답은 100을 출력하면 된다. 만약 총예산이 더 적어서 상한을 90으로 해야한다면 90을 출력해야 한다.

 

오랜만에 2분탐색 문제를 풀어서 재밌었고, 문제를 읽자마자 2분탐색을 써야한다는 게 떠올라서 너무 좋았다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
vector<ll> v;
ll num;
ll m;
ll ans = m;
ll mx;
bool go(ll mid)
{
    // cout << "mid : " << mid << "\n";
    ll sum = 0;
    for (ll i = 0; i < n; i++)
    {
        ll num = v[i];
        if (num > mid)
        {
            sum += mid;
        }
        else
        {
            sum += num;
        }
    }
    if (sum > m)
    {
        return false;
    }
    else if (sum <= m)
    {
        return true;
    }
    return true;
}

int main()
{
    cin >> n;
    for (ll i = 0; i < n; i++)
    {
        cin >> num;
        v.push_back(num);
        mx = max(mx, num);
    }
    cin >> m;
    ll left = 0;
    ll right = m;
    while (right >= left)
    {
        ll mid = (left + right) / 2;
        bool res = go(mid);
        if (res)
        {
            ans = max(ans, mid);
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    ans = min(mx, ans);
    cout << ans << "\n";
    return 0;
}