[C++] 백준 2512: 예산

문제

[C++] 백준 2512: 예산 SILVER 2
https://www.acmicpc.net/problem/2512

 

---

 

접근 방법

이 문제는 각 지방의 예산 요청이 주어졌을 때, 총 예산 M을 넘지 않도록 상한액을 정해 지방 예산을 배정하는 문제이다.

 

핵심은 “상한액을 X로 정했을 때, 각 지방에 min(요청 금액, X)를 배정하면 총합이 M을 넘는가?”를 판단하는 것이다.

상한액이 커질수록 총 배정 예산은 증가하므로, 이 조건은 단조성을 가지게 된다.
따라서 상한액을 대상으로 이분 탐색(Parametric Search) 을 사용할 수 있다.

• 가능한 상한액의 범위: 0 ~ 요청 예산의 최댓값
• mid를 상한액이라고 가정하고 총 배정 예산을 계산
• 총합이 M을 초과하면 상한액을 줄이고

end = (mid - 1);

• 초과하지 않으면 상한액을 더 늘려본다

start = (mid + 1);

 

이 과정을 반복하면 조건을 만족하는 최댓값 상한액을 찾을 수 있다.

 

구현 시 주의할 점

• 이분 탐색의 시작값을 0으로 둬야 한다.
  처음에는 start를 최소 요청 금액으로 잡았는데, 이는 잘못된 설정이었다.
  상한액은 “요청 금액을 줄일 수 있는 기준값”이므로, 이론적으로 0부터 시작해도 전혀 문제가 없고, 오히려 모든 경우를 안전하게 포함할 수 있다.
• mid를 상한액으로 두고 계산한 총합이 M 이하라면
  그 값은 유효한 후보이므로 ret = mid로 저장하고 더 큰 값을 탐색한다.
• 이 방식에서는 갱신되는 mid가 항상 최댓값으로 수렴하므로, 반복문이 끝난 뒤 ret을 그대로 출력하면 된다.
  별도의 조건 검사나 추가 비교는 필요하지 않다.
• 총합과 예산 값이 커질 수 있으므로 long long 타입을 사용해야 오버플로우를 방지할 수 있다.

 

---

 

코드

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

typedef long long LL;

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

	LL n = 0;
	cin >> n;

	LL sum = 0;  // 예산 요청의 총합
	vector<LL> budget(n, 0);
	for (LL i = 0; i < n; i++)
	{
		cin >> budget[i];

		sum += budget[i];
	}
	sort(budget.begin(), budget.end());
	
	LL m = 0;
	cin >> m;

	if (sum <= m)  // case 1
		cout << budget[n - 1];  // 최댓값
	else  // case 2
	{
		LL start = 0, end = budget[n - 1], ret = 0;
		while (start <= end)
		{
			LL mid = (start + end) / 2;

			LL sum2 = 0;
			for (int i = 0; i < n; i++)
				sum2 += min(budget[i], mid);

			if (sum2 > m)
				end = (mid - 1);
			else
			{
				start = (mid + 1);
				ret = mid;
			}
		}
		cout << ret;
	}

	return 0;
}