[BOJ] 2512번 | 예산 (C++)

🔗문제 보러가기

2512번: 예산

 

🧑‍💻풀이 과정

매개변수 탐색으로 풀 수 있습니다. 저는 다음과 같이 풀었습니다.

1. 입력 받은 예산들을 오름차순으로 정렬합니다.
2. 예산들의 합계가 M 이하라면, 예산들 중 최댓값(배열의 마지막 값)을 출력하고 종료합니다.
3. 그게 아니라면, 최소 예산값(1)과 최대 예산값(배열의 마지막 값)을 가지고 이분 탐색을 시작합니다.
   • "mid = (left + right) / 2" 값을 계산합니다.
   • 예산의 총 합계를 계산하되, mid 값보다 큰 예산은 mid 값으로 합계에 더합니다.
   • 다 더한 총 합계가 M 이하라면, left = mid + 1을 하고 max(mid, 이전 mid)로 갱신합니다.
   • 아니라면, right = mid - 1을 적용합니다.
   • left > right가 될 때까지 위 과정을 반복합니다.

 

✏️소스 코드 및 결과

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define FAST_IO cout.tie(NULL); cin.tie(NULL); ios::sync_with_stdio(false);
using namespace std;
using uint32 = unsigned int;

int main()
{
	FAST_IO

	int N;
	cin >> N;

	vector<uint32> budgets(N);
	for (int i = 0; i < N; i++)
		cin >> budgets[i];

	sort(budgets.begin(), budgets.end());
	uint32 start = 1, last = budgets.back();
	
	uint32 M;
	cin >> M;

	if (accumulate(budgets.begin(), budgets.end(), 0) <= M)
	{
		cout << budgets.back();
		return 0;
	}


	uint32 answer = 0;
	while (start <= last)
	{
		uint32 mid = (start + last) / 2;
		uint32 money = 0;

		for (const auto& budget : budgets)
			money += (budget <= mid) ? budget : mid;

		if (money <= M)
		{
			start = mid + 1;
			answer = max(answer, mid);
		}
		else
			last = mid - 1;
	}

	cout << answer;
	return 0;
}