백준 2512 - 예산 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/2512

풀이전략

1. 문제에서 모든 요청이 가능하면 그 금액을 주고, 아니라면 상한액을 설정해서 그 이상의 금액은 뺴고 상한액만큼만 준다. 즉 문제에서는 상한액을 찾아야 하는 문제이다.
2. 갯수가 상당히 많으므로 이는 반드시 이분검색으로 찾아야한다.

코드

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> budget;
int N, M;
long long findBudget(int val){
    long long sum = 0;
    for(int i=0; i<budget.size(); i++){
        if(budget[i] < val){
            sum += budget[i];
        }
        else sum += val;
    }
    return sum;
}
int res = 0;
int BinarySearch(int lt, int rt){
    if(lt > rt){
        return res;
    }
    else{
        int mid = (lt+rt) / 2;
        long long midVal = findBudget(mid);

        if(midVal <= M){
            res = max(res, mid);
            return BinarySearch(mid+1, rt);
        }
        else{
            return BinarySearch(lt, mid-1);
        }
    }
}

int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d",&N);
    int tmp, mm = 0;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        if(tmp > mm) mm = tmp;
        budget.push_back(tmp);
    }

    scanf("%d",&M);
    printf("%d\n", BinarySearch(1, mm));

    return 0;
}

소감

이번 문제는 상한액을 이분검색으로 찾는 문제였다. 이런 문제처럼 이분 탐색이 아닌 것처럼 문제를 만들어도 이 문제가 이분 탐색인지 아닌지 구별할 수 있어야 한다.