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

문제링크

설명

이 문제도 value를 기준으로 이분탐색을 진행한다.
각 예산이 정해져있으니 가장 큰 예산으로 가운뎃값을 구하고 합을 구한후
목표치보다 작은 경우 가운뎃값을 늘려주거나 줄이기 위해 범위를 조정한다.

제출 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

	int n, m;
	cin >> n;
	vector<int> v(n);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	cin >> m;

	sort(v.begin(), v.end());

	int left = 0;
	int right = v.back();
	int result = 0;

	while (left <= right)
	{
		int sum = 0;
		int mid = (left + right) / 2;

		for (int i = 0; i < n; i++)
			sum += min(v[i], mid);

		if (m >= sum)
		{
			result = mid;
			left = mid + 1;
		}
		else
			right = mid - 1;
	}

	cout << result;

	return 0;
}