[BOJ][실3][2512] 예산

문제 링크

문제링크

첫 번째 풀이 : 이분 탐색

알고리즘

이분 탐색을 사용해서 풀이합니다.

정답이 될 수 있는 가능성이 있는 범위는 [LEFT, RIGHT]로 정의합니다. 이 안에서 이분탐색을 진행하면서 문제의 조건을 만족하는지는 check()에서 확인합니다.

LEFT가 0이라면 check()함수에서 런타임 에러 (DivisionByZero)가 발생할 수 있으니 1부터 시작합니다.

정답코드

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 10'010;

ll n = 0, k = 0;
ll ans = 0;

vector<ll> arr(MAX);
ll sum[MAX];
ll LEFT = 1;
ll RIGHT = 0;

bool check(ll x) {
    ll ret = 0;
    for (int i = 0; i < n; i++) {
        if (x < arr[i]) ret += x;
        else ret += arr[i];
    }
    
    return ret <= k ? true : false;
}

int main(void) {
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
        RIGHT = max(RIGHT, arr[i]);
    }
    cin >> k;

    while (LEFT <= RIGHT) {
        ll MID = (LEFT + RIGHT) / 2;
        if (check(MID)) {
            LEFT = MID + 1;
            ans = max(ans, MID);
        }
        else {
            RIGHT = MID - 1;
        }
    }
    cout << ans;
    return 0;
}

Success Notice: 수고하셨습니다.