[C++] 백준 2512 : 예산

문제

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

 

 

 

풀이

  입력과 함께 요청 금액의 합을 계산(-> 이후 상한액 설정 필요 여부 결정)하고, 동시에 요청 금액의 최댓값( -> 바로 결과를 출력하거나 이분 탐색 시 right의 초기값으로 이용)을 계산한다.

 

  이후 상한액 설정이 필요한 경우(예산 < 요청 금액 합), 이분탐색으로 최대 상한액을 구한다.

 

  구체적인 구현 방식은 아래 코드의 주석을 참고하면 된다.

 

 

 

코드

#include <iostream>
#include <string>
using namespace std;

long long n, sum_all, M, max_arr;
long long arr[10000];
int main()
{
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> arr[i];
        
        // 요청 금액의 합 계산
        sum_all += arr[i];
        
        // 요청 금액의 최댓값 계산
        if(arr[i] > max_arr) max_arr = arr[i];
    }
    
    cin >> M;
    
    // 요청 금액을 모두 할당할 수 있는 경우, 요청 금액의 최댓값 출력
    if(sum_all <= M) cout << max_arr << "\n";
    
    // 요청 금액을 모두 할당할 수 없는 경우, 
    else{
    
        // 이분탐색
        int left = 0, right = max_arr;
        int max_ans=0;
        while(left <= right){
        
            // left와 right의 중간값이 이번 탐색에서 사용할 상한액
            int mid = (left + right)/2;
            if(mid == max_ans) break;
        
            int cur_sum = 0;
            for(int i=0; i<n; i++){
            
                // 상한액보다 요청 금액이 작다면 요청 금액을 합계에 더함
                if(arr[i]<mid) cur_sum+=arr[i];
                
                // 상한액보다 요청 금액이 크다면 상한액을 합계에 더함
                else cur_sum+=mid;
                
                // 만약 합계가 예산보다 커졌다면, 어차피 해당 mid를 상한액으로 사용할 수 없으므로 break
                if(cur_sum > M) break;
            }
            
            // 합계가 예산을 초과한 경우, 상한액을 줄여야 함.
            if(cur_sum > M) right = mid;
            
            // 예산 할당이 가능한 경우, 상한액을 늘려야 함.
            else if(cur_sum > max_ans){
                max_ans = mid;
                left = mid;
            }
        }
        cout << max_ans << "\n";
    }
    return 0;
}