[백준/C++] 2512번 예산

2512번: 예산

풀이

이분 탐색을 이용해 배정된 예산 중 최대값을 출력한다.

국가 예산 총액보다 지방의 예산 요청 금액의 합이 클 경우 임의로 예산 상한액을 정한다. 요청 예산이 상한액을 초과할 경우 상한액만큼만 배정하고, 상한액 이하일 경우엔 요청 금액을 그대로 배정한다.

예산 상한액을 mid로 설정하여 배정될 예산 금액의 합을 구하고, 이 값이 국가 예산 총액 이하이면서 최대일 때를 구한다. 이때 배정된 예산 중 최대값인 예산 금액을 출력해야 한다.

코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int money[10001] = {0}, n = 0, m = 0;
  cin >> n;
  for (int i = 0; i < n; i++)
    cin >> money[i];
  cin >> m;
    
  int left = 1, right = money[n - 1], result = 0;
  while (left <= right){
    int mid = (left + right) / 2, sum = 0;
		
    for (int i = 0; i < n; i++){  // 배정될 예산의 총합
      if (money[i] > mid)
        sum += mid;
      else
        sum += money[i];
    }
    if (sum > m)       // 예산 상한액 감소
      right = mid - 1;
    else{
      left = mid + 1;  // 예산 상한액 증가
      result = mid;
    }
  }
  cout << result;
  return 0;
}