[백준 2512] 예산 (C#, C++) - soo:bak

문제 링크

2512번 - 예산

설명

각 지방의 예산 요청과 총 예산이 주어질 때, 모든 요청을 만족시키거나 상한액을 정해 배정할 수 있는 최대 상한액을 구하는 문제입니다. 요청액이 상한액 이하면 그대로, 초과하면 상한액만큼 배정합니다.

접근법

모든 요청의 합이 총 예산 이하라면 가장 큰 요청액이 그대로 답이 됩니다.

그렇지 않다면 이분 탐색으로 적절한 상한액을 찾습니다. 상한액의 범위는 0부터 가장 큰 요청액 사이입니다.

중간값을 상한액으로 정했을 때, 각 요청에 대해 요청액과 상한액 중 작은 값을 배정한 총합을 구합니다. 이 총합이 총 예산 이하라면 상한액을 더 올릴 수 있으므로 현재 값을 저장하고 탐색 범위를 오른쪽으로 이동합니다. 총합이 총 예산을 초과한다면 상한액을 낮춰야 하므로 탐색 범위를 왼쪽으로 이동합니다.

탐색이 끝나면 저장된 값이 조건을 만족하는 최대 상한액입니다.

---

Code

C#

using System;
using System.Linq;

class Program {
  static void Main() {
    var n = int.Parse(Console.ReadLine()!);
    var req = Console.ReadLine()!.Split().Select(int.Parse).ToArray();
    var m = int.Parse(Console.ReadLine()!);

    var lo = 0;
    var hi = req.Max();
    var ans = 0;
    while (lo <= hi) {
      var mid = (lo + hi) / 2;
      var sum = 0L;
      foreach (var x in req) sum += x > mid ? mid : x;

      if (sum <= m) {
        ans = mid;
        lo = mid + 1;
      } else hi = mid - 1;
    }

    Console.WriteLine(ans);
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  vi req(n);
  for (int i = 0; i < n; i++) cin >> req[i];
  int m; cin >> m;

  int lo = 0, hi = *max_element(req.begin(), req.end()), ans = 0;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    ll sum = 0;
    for (int x : req) sum += (x > mid ? mid : x);

    if (sum <= m) {
      ans = mid;
      lo = mid + 1;
    } else hi = mid - 1;
  }

  cout << ans << "\n";

  return 0;
}