[2512] 예산 C++

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

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	int N, M;
	int arr[10001];
	cin >> N;

	int sum = 0;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	cin >> M;
	sort(arr, arr + N);

	if (sum <= M) {
		cout << arr[N - 1];
		return 0;
	}

	else {
		int left = 0;
		int right = arr[N - 1];

		int answer;
		while (left <= right) {
			sum = 0;
			int middle = (left + right) / 2;

			for (int i = 0; i < N; i++) 
				sum += min(arr[i], middle);

			if (sum == M) {
				cout << min(arr[N - 1], middle);
				return 0;
			}

			else if (sum > M)
				right = middle - 1;

			else {
				left = middle + 1;
				answer = min(arr[N - 1], middle);
			}
		}

		cout << answer;
	}
	
	return 0;
}