[C++] 백준 2512 - 예산

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

2512번: 예산

<알고리즘 분류>

   -  이분 탐색 (Binary Search)

 

<풀이> 

  1. 국가예산의 총액은 한정되어 있고, 여러 지방의 예산 요청액은 국가 예산 총액을 넘어설 수도 있다. 

그렇기에 여러 지방의 예산 요청액을 최대한 충족하는 선에서, 국가예산 총액을 최대한 써야 한다(상한가 지정).

  2. 상한가 지정은 Binary Search 로 진행을 한다.  

 

<주의사항>

  1. Binary Search 진행 시에 low, mid, high 관계를 잘 파악해야 한다. 정답이 100이라면, 101 또는 99로 정답이 나와 마지막에서 헤매는 경우가 매우 많다. 

    가령 예를 들어 보자. 

우리는 정답 4를 원하는 상황인데,

                                    low         mid          high 

                                       3                                 4

인 상황에서는 mid가 3만 나와서 이것만으로는 결괏값을 도출하기 어렵다.

따라서! low = mid + 1; 을 해주어야 한다

또한 while(high >= low)문을 벗어나기 위해서는 low가 high보다 높아야 하는데, 그 경우 결괏값을 한시적으로 저장해 줄 수 있는

int result = mid; 

를 두어 정답값을 보존한다. 

 

이분탐색이 항상 -1, 1 차이로 정답을 맞추지 못하는 경우가 많았는데, 이번 문제를 기점으로 조금 더 정교하게 풀 수 있을 것 같다.

   

<코드>

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

int N; // 지방의 수 
int RequestMoney[10001]; // 각 지방별 예산요청액 
int high = 0; //상한액 

int main(){
    cin >> N;
    for (int i=0; i<N; i++){
        cin >>RequestMoney[i];
        if (high < RequestMoney[i]) high = RequestMoney[i];
    }
    long long SumRequest; // 국가에서 정해진 총 예산
    long long sum = 0; // 임시 상한가(mid) 지정 시 계산되는 예산 
    cin >> SumRequest;

    int low = 0;
    int mid, result ;

    while(high >= low ){
        mid = (high + low ) / 2 ;    
        sum = 0;
        
        for (int i=0; i< N; i++){
            sum += min(RequestMoney[i], mid);
        }

        if (sum <=SumRequest){ // 예산액을 초과하지 않는 경우(넉넉할 떄 )
            low = mid+1;
            result = mid;
        }
        else // 예산액을 초과하는 경우 
            high = mid-1;
     
    }

    cout << result; 


}