언제나 처음처럼

[문제 링크]

https://onlytrying.tistory.com/55

1654번: 랜선 자르기, 2805번: 나무 자르기 유형의 문제와 같은 알고리즘을 사용한다.

분배하는 예산이 커질 수록 총 필요한 예산도 커진다. 즉, 분배하는 예산과 총 필요한 예산은 서로 비례한다.

금액 N으로 예산을 분배했을 때 만약 총 필요한 예산이 입력받은 국가 예산보다 크다면 N 이상의 금액을 고려하지 않아도 되기 때문에 이분 탐색을 진행할 수 있다.

먼저, 지방 예산을 vector 배열에 저장하면서, 변수 sum에 누적한다.

만약 입력받은 국가 예산이 sum보다 크다면 정답은 가장 큰 지방 예산이 되기 때문에 탐색을 하지 않아도 된다.

이 경우가 아니라면 start를 1, end를 가장 큰 지방 예산으로 이분 탐색을 진행하여 가능한 최대 예산을 구해주면 된다.

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

int main(void)
{
	int N;
	cin >> N;
	
	vector<int> money(N);
	int total = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> money[i];
		total += money[i];
	}

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

	int maxMoney;
	cin >> maxMoney;

	if (total <= maxMoney)
		cout << money[N - 1];
	else
	{
		int start = 1, end = money[N - 1], result;
		
		while (start <= end)
		{
			int mid = (start + end) / 2, sum = 0;
			for (int i = 0; i < N; i++)
			{
				if (money[i] <= mid)
					sum += money[i];
				else
					sum += mid;
			}
			
			if (sum <= maxMoney)
			{
				result = mid;
				start = mid + 1;
			}
			else
				end = mid - 1;
		}

		cout << result << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 46 day