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

 

문제 2512번

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

2512번: 예산

 

이진탐색을 해주기 위해 입력받은 값들을 오름차순으로 정렬해주었다. 그리고 v에 있는 입력값과 기준으로 잡은 상한액인 mid와 비교하여 작은 값을 count에 더해준다. 그렇게 나온 합이 총 예산보다 작거나 같으면 result에 해당 상한액인 mid를 넣어주고 start는 mid에 1증가시켜준다. 반대인 경우, end는 mid에 1감소시켜준 값을 넣어주면 된다.

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

int main() {
	int N, M, result = 0;
	cin >> N;
	vector <int> v(N);
	for (int i = 0; i < N; i++) {
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	cin >> M;	//총 예산
	int start = 0, end = v[N - 1];
	while (start <= end) {
		int count = 0;
		int mid = (start + end) / 2;
		for (int i = 0; i < N; i++) {
			count += min(v[i], mid);
		}
		if (M >= count) {
			result = mid;
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}
	cout << result;

	return 0;
}