[ BOJ 백준 2512번 - 예산 ] 해설 및 코드

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

목적

지방예산을 모두 더해서 국가예산에 최대한 가깝게 만들 수 있도록 상한액을 정하라.

 

접근법

1. 상한액을 1씩 더하거나 빼서 구하려고 하면,  시간초과가 발생하므로 이분 탐색 알고리즘을 이용하여 접근한다.

 

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,a[10001],ret;
void bs(int l,int r){
    if(l>r){
        ret=r;
        return;
    }
    
    int h=(l+r)/2;
    
    long long k=0;
    for(int i=0;i<n;++i) k+=(a[i]<h?a[i]:h);
    
    if(k<=m) bs(h+1,r);
    else bs(l,h-1);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n;
    int tmp=0;
    for(int i=0;i<n;++i){
        cin>>a[i];
        if(tmp<a[i])tmp=a[i];
    }
    cin>>m;
    
    bs(0,tmp);
    cout<<ret;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.