예산 2512

문제

접근 방법

아직 낮은 단계에 문제라서 비슷비슷한 것 같다.
합계를 낼 때 상한액을 넘지 못하게 해주면 된다.

코드

#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M, ret = 0;
    cin >> N;
    vector<int> moneys(N);
    ll low = 0, mid, high = 0;
    for (int i = 0; i < N; ++i)
    {
        int money;
        cin >> money;
        moneys.push_back(money);
        if (high < money)
            high = money;
    }
    cin >> M;
    while (low <= high)
    {
        mid = (low + high) / 2;
        ll sum = 0;
        for (int money : moneys)
            sum += ((money <= mid) ? money : mid);
        if (sum <= M)
        {
            low = mid + 1;
            if (ret < mid)
                ret = mid;
        }
        else
            high = mid - 1;
    }
    cout << ret;
    return 0;
}

풀이

int 범위를 넘을 수 있을 것 같아서 long long으로 선언해줬다.