[BOJ/2512번예산] c++ / 이진탐색

문제

배정된 예산액의 최댓값을 구하는 문제

-모든 요청이 배정될 수 있는 경우, 요청한 그대로 배정함

-모든 요청이 배정될 수 없는 경우, 특정 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정함

 

생각

배열의 인덱스로 이진탐색을 할지, 예산 요청액으로 이진탐색을 할지 생각함

이 문제는 예산 요청액의 최댓값을 구하는 문제라 후자로 풀어야겠다 생각함

문제풀이

1.예산 요청액 중 최댓값을 찾음 ( 예산액 st = 1, end = 최댓값 )

2.st < end면 반복문 실행

2-1.mid = (st+end) / 2

2-2.solve를 만족한다면, st = mid+1

2-3.만족하지 않는다면, end = mid-1

-solve

1.sum에 예산액을 모두 더함 ( 상한액보다 작으면 그대로, 크면 상한액을 더해줌 )

2.배정된 예산보다 적다면 true 반환

3.st 출력

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
int n, budget;
int a[100001];
bool solve(int uplim) {
    int sum = 0;
    for ( int i = 0; i < n; i++ ) 
        sum += min(a[i], uplim); // uplim보다 작은 예산은 그대로, uplim보다 큰 예산은 상한액을 더해줌
    return budget >= sum;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    int st = 1, en = 1;
    for ( int i = 0 ; i < n; i++ ) {
        cin >> a[i];
        en = max(a[i], en);
    }
    cin >> budget;

    while ( st < en ) {
        int mid = (st + en + 1) / 2;
        if ( solve(mid) ) st = mid;
        else en = mid-1;
    }
    cout << st;
}