[C++] 백준 2512번 - 예산

이진탐색을 활용하는 문제

생각보다 이진탐색할때 조건을 설정하는 부분이 어려웠다

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

long long arr[10001];

int main() {

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

	int budget;
	cin >> budget;

	sort(arr, arr + n);

	long long low = 0;
	long long high = arr[n - 1];

	if (sum <= budget) {
		cout << arr[n - 1] << '\n';
	}
	else {
		while (low + 1< high) {
			long long mid = (low + high) / 2;
			long long temp_budget = 0;

			for (int i = 0; i < n; i++) {
				if (arr[i] >= mid) {
					temp_budget += mid;
				}
				else
					temp_budget += arr[i];
			}

			if (temp_budget > budget) {
				high = mid;
			}
			else if (temp_budget <= budget) {
				low = mid;
			}
		}
		cout << low << '\n';
	}
	return 0;
}