[백준][이분탐색] 2512번 예산

문제

각 나라별 필요한 예산과 총 예산이 주어지고, 가장 최대한의 예산을 써서 각 나라에 배정하는 예산의 상한액을 구하시오.

문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/2512), 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/43237) 

풀이

이분탐색을 통해서 푸는 문제입니다. 최대한 많은 예산을 나눠야하고, 해당 상한액보다 작은 경우엔 모두 배정해줄 수 있고 상한액보다 높다면 상한액까지 배정해줄 수 있습니다. 사실 이 문제를 통해서 이분탐색을 활용해서 푸는 문제를 처음 다뤄볼 수 있었고 처음에 이분탐색 카테고리라는 걸 알았지만 어떻게 이분탐색을 적용해야하는지 감이 오지 않았습니다.(이분탐색에 대한 개념이 없으신 분들을 개념에 대한 포스팅을 먼저 보는 걸 추천합니다.) 이분탐색을 적용해야한다는 포인트는 가능한 최대한의 예산을 배정하는 것인데, 그러한 가능한 예산범위를 줄여가다보면 마지막에는 최대한의 예산인 금액으로 남게 됩니다. 배정할 수 있는 총 예산이 500이라면 [0, 500]이라는 예산범위에서 시작할 수 있습니다. 0원씩 배정을 한다면 예산을 초과하지 않기 때문에 배정이 가능합니다. 총 예산이 500이라면 500씩 모든 나라에 배정하게 되면 예산범위를 초과할 것이기 때문에(나라가 1개가 아니라면) 불가능합니다. 여기서 포인트는 한 쪽은 조건을 만족하고 한 쪽은 만족하지 않는다는 것입니다. 500은 조건을 만족하지 않기 때문에 줄여야합니다. 이 때 이분탐색을 위해 low = 0, high = 500이므로 mid = 250으로 조건을 만족하는지 확인을 해줍니다. 만약 250이 조건을 만족한다면 더 많은 예산을 배정할 수 있을지 탐색해야하므로 low = mid 으로 범위를 줄여 탐색해나가고, 조건을 만족하지 않는다면 high = mid 로 탐색을 해나갑니다. 이 문제에서는 범위를 계속 줄여나가면서 탐색을 하는데 처음 시작할 때 low인 0이 만족하는 쪽이었으니 계속해서 low쪽의 값은 조건을 만족하는 값일 것이고 만약 계속해서 줄이다가 더이상 줄일 수 없는 시점이 왔을 때 low의 값이 조건을 만족하는 최대값이 됩니다. 이러한 이분탐색을 이용하는 문제들은 대부분 쉽게 느껴져서 다른 방법으로 풀 수 있기도 하지만 시간초과를 피할 수 없습니다. 

코드

#include<cstdio>

#include<vector>

#include<algorithm>

using namespace std;

int main(){

int N, tmp, money;

int low, high, mid;

int sum=0;

vector<int> budgets;

scanf("%d", &N);

for(int i=0; i<N; i++){

scanf("%d", &tmp);

budgets.push_back(tmp);

sum += tmp;

}

scanf("%d", &money);

sort(budgets.begin(), budgets.end());

if(sum <= money){

printf("%d", budgets[budgets.size()-1]);

}

else{

low = 0;//0원씩 편성해주면 조건 만족(but 최소한 x)

high = money; //sum<tmp 이므로 가장 큰 예산을 모두에게 편성하면 조건 만족 못함

while(low+1 < high){

mid = (low+high)/2;

sum = 0; 

for(int i=0; i<budgets.size(); i++){

if(budgets[i] < mid)

sum += budgets[i];

else

sum += mid;

}

if(sum <= money)

low = mid;

else 

high = mid;

}

printf("%d\n", low);

}

return 0;

}