[백준] 2512 예산

 

 

이진탐색문제이다.

요청된 예산을 벡터에넣어 정렬한 후, (1~벡터원소중 가장 큰 값)의 범위에서 이진탐색을 진행한다.

예산범위 내에서 최대 상한선을 구한다? -> 이진탐색을 끝마쳤을 때 high값이 최대가 된다.

 

Code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int n, budget;
vector<int> v;
 
int main()
{
    cin >> n;
    v.resize(n);
    for (int i = 0; i < n; i++)
        cin >> v[i];
    cin >> budget;
 
    sort(v.begin(), v.end());
 
    int high = v[n - 1];
    int low = 0;
    int mid;
    while (low <= high)
    {
        mid = (low + high) / 2;
        int sum = 0;
        cout << high << " ";
        for (int i = 0; i < n; i++) //상한액을 mid로 했을 때 총합계산 
        {
            if (v[i] <= mid)
                sum += v[i];
            else
                sum += mid;
        }
 
        if (sum > budget) //총예산보다 많다면 상한액을 줄여본다.
            high = mid - 1;        
        else //총예산보다 적다면 상한액을 늘려본다.
            low = mid + 1;
    }
 
 
}