메모리

시간

1116 KB

0 ms

Code

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int n;
	int fin, start, mid, end = 0;
	scanf("%d", &n);
	int budg[10001];
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &budg[i]);
		if (budg[i] > end)
			end = budg[i];
	}
	int m;
	scanf("%d", &m);
	while (start <= end)
	{
		fin = 0;
		mid = (end + start) / 2;
		for (int i = 0; i < n; i++)
		{
			if (budg[i] > mid)
			fin += mid;
			else
			fin += budg[i];
		}
		if (fin <= m)
			start = mid + 1;
		else
			end = mid - 1;
	}
	printf("%d", end);
	return 0;
}

문제 풀이

정해진 예산 내에서의 최대값을 구하는 문제이다.

점차 범위를 줄여나가면서 start 와 end를 구해 중간값을 찾고

중간값을 기준으로 만약 각 지역에서 요청하는 값이 더 적다면 해당 값을, 더 크다면 중간값을 더해가며

fin을 구하고 fin을 m과 비교하며 범위를 줄여나간다.

범위가 딱 1개의 값이 될때 end를 출력하여 최대값을 출력해주었다.