백준 - 2512번 : 예산 (C++)

풀이 방법 : 이분 탐색

이 문제에서 배정된 예산들 중 최댓값인 정수를 출력하라는 것은 가능한 예산 상한선의 최댓값을 출력하라는 것과 같다.
그럼 예산 상한선의 최댓값을 찾아내면 되는데, 이처럼 특정 범위 내에서 최댓값을 찾아내는 문제는 이분탐색을 고려해볼만 하다.

특정 1차원 범위 내에서 추정 상한선을 구하고 그 상한선에 따라 예산 내에서 모든 요청에 대해 배정이 가능한지(참/거짓)를 따질 수 있으므로 이분 탐색으로 푸는 것이 적당할 것이다.

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

using namespace std;

int main()
{
	int N;
	cin >> N;

	vector<int> vecRequest(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> vecRequest[i];
	}

	int Max;
	cin >> Max;

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

	int Left = 0;
	int Right = vecRequest[N - 1];

	int Answer = 0;

	while (Left <= Right)
	{
		int Sum = 0;
		int Mid = (Left + Right) / 2;

		for (int i = 0; i < N; ++i)
		{
			if (vecRequest[i] < Mid)
				Sum += vecRequest[i];

			else
			{
				Sum += Mid * (N - i);
				break;
			}
		}

		if (Sum > Max)
		{
			Right = Mid - 1;
		}

		else
		{
			Left = Mid + 1;
			Answer = max(Mid, Answer);
		}
	}
	
	cout << Answer;
}