[백준] 2512번 : 예산

https://www.acmicpc.net/problem/2512

2512번: 예산

<C++>

#include <bits/stdc++.h>
#include <limits.h>
typedef long long ll;
using namespace std;
ll a[10004];
int n;
ll m;
int pos(int mid)
{
	ll sum = 0;
	for (int i = 0; i < n; i++)
	{
		if (mid >= a[i])
			sum += a[i];
		else
			sum += mid;
	}
	return (sum <= m);
}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	cin >> m;


	ll s = 1, e = 0, ans = 1; //s : 최소값, e : 최대값, ans : 정답
    
	for (int i = 0; i < n; i++)
		e = max(e, a[i]); //e는 a[i]들의 값들 중 가장 큰 값으로 결정
        
	while (s <= e)
	{
		ll mid = (s + e) / 2;
		if (pos(mid)) //m보다 sum이 작다면
		{
			ans = max({ ans,mid }); //값 비교해서 최대값을 저장해놓기
			s = mid + 1;
		}
		else
			e = mid - 1;
	}
	cout << ans << '\n';
}

---

 

<주의 해야 할 부분>

 

1. e(최대값)의 시작값을 잘 정하자

2. 예산들 중 최대값을 출력해야 한다. pos 함수에서 만족하는 값이 여러개라는 의미이다. 그 중 최대값을 고르는 문제