[Algorithm]Baekjoon 2512번 :: 예산

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
int arr[10001] = { 0 };
 
bool check(int mid)
{
    int sum = 0;
 
    for (int i = 0; i < n; ++i)
    {
        if (arr[i] < mid) sum += arr[i];
        else sum += mid;
    }
 
    if (sum <= m) return true;
    return false;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    int maxNum = 0;
    int sum = 0;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> arr[i];
 
        sum += arr[i];
        maxNum = max(maxNum, arr[i]);
    }
 
    cin >> m;
 
    if (sum <= m)
    {
        cout << maxNum;
        return 0;
    }
 
    int left = 0;
    int right = m; 
    int answer = 0;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            left = mid + 1;
            answer = mid;
        }
        else
        {
            right = mid - 1;
        }
    }
 
    cout << answer;
}
 
 
 

 

요구예산금액의 누적값이 배정받은 예산을 초과할 경우, 임의의 수인 상한액을 구해야하는 문제이다.

즉, 상한액을 구해서 이 상한액을 넘는 요구예산금액은 전부 이 상한액으로 치환해서 누적시킨다. 당연히 이 누적액은 배정예산을 넘어서면 안된다.

 

정확히 문제에서 요구하는 출력은 최대로 배정한 예산금액인데, 처음에 요구예산금액에 대한 정보를 입력받을때 전부 합산한 금액이 배정예산보다 작으면 그냥 제일 큰값을 출력하면 된다..

만약 초과할경우에는 결국 임의의 상한액을 구해야하고, 이 상한액자체가 최대로 지역에 배정하는금액이 되니 이 임의의 상한액을 출력해주면 된다.