2512번: 예산

Memo

로직 설명

• 예산의 상한액을 결정하고, 그 값과 예산 요청 값들의 최소값을 모두 더합니다.
• 더한 값이 M보다 작으면 상한액을 올리고, 크거나 같으면 상한액을 내립니다.
• 더한 값이 M이랑 같거나 작아지면 그 값이 정답입니다.

Code

제출 날짜

2021/04/15

메모리

2056 KB

시간

0 ms

#include <iostream>
#include <algorithm>

int N, M, MAX_, ans;
int request[10001];

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N;
	MAX_ = 0;
	for (int i = 0 ; i < N ; i++)
	{
		std::cin >> request[i];
		if (MAX_ < request[i])
			MAX_ = request[i];
	}
	std::cin >> M;
}

void solve()
{
	int left = 0, right = MAX_, mid, cnt;

	while (left <= right)
	{
		mid = (left + right) / 2;
		cnt = 0;
		for(int i = 0 ; i < N ; i++)
			cnt += std::min(mid, request[i]);
		if (cnt <= M)
			left = mid + 1;
		else
			right = mid - 1;
	}
	ans = right;
}

void print_val()
{
	std::cout << ans;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}