[C/C++ 백준 2512번] 예산 (Silver 3)

www.acmicpc.net/problem/2512

2512번: 예산

평범한 이분 탐색 문제이지만, 정답이 각 지방 예산중 최댓값을 출력하는 것임을 유의하자.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int main(void){
	long long int N, array[10001], arraymax = -1, maxmoney, ans = -1;
	scanf("%lld", &N);
	for(int i=0; i<N; i++){
		scanf("%lld", &array[i]);
		arraymax = max(array[i], arraymax);
	}
		
	scanf("%lld", &maxmoney);
	long long int left = 0, right = 100000, mid, money;
	while(left <= right){
		money = 0;
		mid = (left + right)/2;
		for(int i=0; i<N; i++){
			if(array[i] < mid)
				money += array[i];
			else
				money += mid;
		}
		if(money <= maxmoney){
			ans = max(ans, mid);
			left = mid + 1;
		}
		else
			right = mid - 1;
	}
	if(arraymax < ans)
		printf("%d", arraymax);
	else
		printf("%lld", ans);
}