예산 (feat. 백준, 2512번)

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

2512번: 예산

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, M, arr[10000], sum, ans;
    cin >> N;
    for(register int n = 0; n < N; ++n)
        cin >> arr[n];
    cin >> M;
    // auto mm = minmax_element(arr, arr + N);
    // register int low = *mm.first, high = *mm.second, mid;
    register int low = 0, high = *max_element(arr, arr + N), mid;
    while(low <= high){
        sum = 0;
        mid = (low + high) / 2;
        for(register int i = 0; i < N; ++i)
            sum += min(arr[i], mid);
        if(sum <= M)
            ans = mid, low = mid + 1;
        else if(sum > M)
            high = mid - 1;
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

1. 이진탐색으로 중간값을 선택합니다.
2. 중간값과 입력받은 P0, P1, P2 각각에 대해서 둘 중 최소값을 누적합니다. ( min(mid, P0) + min(mid, P1) + ...)
3. 누적값과 입력받은 M값을 통해 이진탐색의 low와 high를 조정합니다.
4. 주의할 점은 low는 입력값의 최소값이 아니라 0부터 수행되어야 한다는 점입니다.