[백준 C++] 2512 예산 - 이분탐색

2512번: 예산

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

vector<int> Weights;

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

	int N;
	cin >> N;

	Weights.reserve(N);
	for (int i = 0; i < N; ++i)
	{
		int Weight;
		cin >> Weight;
		Weights.emplace_back(Weight);
	}

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

	int M;
	cin >> M;

	int Solution = 0;
	int Left = 0;
	int Right = M;
	while (Left <= Right)
	{
		int Mid = (Left + Right) / 2;
		
		int Count = 0;
		int MaxWeight = 0;
		for (const int& Weight : Weights)
		{
			if (Weight < Mid)
			{
				Count += Weight;
				MaxWeight = max(MaxWeight, Weight);
			}
			else
			{
				Count += Mid;
				MaxWeight = max(MaxWeight, Mid);
			}

			if (Count > M)
			{
				break;
			}
		}

		if (Count <= M)
		{
			Solution = MaxWeight;
			Left = Mid + 1;
		}
		else
		{
			Right = Mid - 1;
		}
	}

	cout << Solution;
}

---

 

이분탐색으로 배정 금액의 상한선을 찾는 문제입니다.

유의할 점은 최종적으로 찾은 상한 금액을 출력하는 것이 아니라

상한 금액을 찾았을 때의 가장 큰 분배 금액을 출력해야 하는 것입니다.