[백준 2512] 알고리즘 61일차 : 예산

www.acmicpc.net/problem/2512

2512번: 예산

C++ 이분탐색

연초에 시기적절한 문제인 것 같아서 풀어봤다(변명)

이분탐색은 진짜 한번 풀면 계속 풀 수 있을 것 같다(그러면서 왜 골드는 안푸는데요)

아무튼.

 

접근방법

지방의 예산요청액 입력받을때 합이랑 최댓값 같이 구해놓고

합이 전체 국가 예산보다 작으면 최댓값 출력하고 끝. 아니면

이분탐색 함수 부를때 (1,최댓값)으로 범위설정해서 보내고

 

이분탐색 기준 함수는 지방 예산요청액 배열 다 돌면서 상한액이랑 비교하면서

상한액 미만이면 배열에 있던 값을 더하고 아니면 상한액을 total에 더한다.

마지막에 전체 국가예산이랑 total이랑 비교해서 국가예산 이하면 true, 초과면 false 리턴

 

소스코드

#include <iostream>
using namespace std;
int N,M;
int budget[200000];
bool isUnder(int max){
    int total = 0;
    for(int i = 0 ; i < N ; i++){
        if(max > budget[i]){
            total += budget[i];
        }else{
            total += max;
        }
    }
    return total <= M ? true : false;
}
int binarySearchMax(int s, int e){
    int mid = 0;
    while(s <= e){
        mid = (s+e)/2;
        if(isUnder(mid)){
            s = mid+1;
        }else{
            e = mid-1;
        }
    }
    return s-1;
}
int main(){
    cin >> N;
    int max = 0;
    int sum = 0;
    for(int i = 0 ; i < N ; i++){
        cin >> budget[i];
        sum += budget[i];
        if(max < budget[i])
            max = budget[i];
    }
    cin >> M;
    
    if(sum <= M){
        cout << max;
    }else{
        cout << binarySearchMax(1, max);
    }
    return 0;
}