백준2512 - 예산

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

2512번: 예산

이진탐색으로 푼 문제다. 이진탐색으로 풀어야 하니까 오름차순을 적용하였다. 예산을 찾을 때 가장 작은 예산을 찾는 범위의 시작으로 놓으면 틀린다. 왜냐하면 예산 총액이 처음에 불렀던 예산보다 작을 수 있기 때문이다. 이점을 지키고 예산을 찾았다면 답을 현재 찾은 예산으로 갱신하고 시작값을 현재 찾은 예산 + 1로 갱신한다.

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

int main() {
	int n; //지방 자치단체 수
	int num; //예산
	int limit; //예산 총액
	int res = 0; //처음에 불렀던 예산을 모두 더한 결과
	int x; //답으로 채택할 최대 예산
	vector<int> v; //예산들의 정보

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		v.push_back(num);
		res = res + num;
	}
	
	sort(v.begin(), v.end()); //오름차순 정렬
	
	cin >> limit;

	x = v[v.size() - 1];

	if (limit >= res) {
		cout << x;
	}
	else {
		int left = 0; //제일 처음 주어진 예산보다 총액이 작은 예산이 들어올 수 있음으로 v[0]라 하면 틀림
		int right = v[v.size() - 1]; //최대 예산

		//이진 탐색을 통하여 최대가 될 수 있는 예산을 찾는다.
		while (left <= right) {
			int ans = 0;
			int mid = (left + right) / 2;
			for (int i = v.size() - 1; i >= 0; i--) {
				int temp = v[i];
				if (temp > mid) { //처음에 불렀던 예산이 현재 찾은 예산보다 큰 경우
					temp = mid; //현재 찾은 예산으로 초기화
				}
				ans = ans + temp;
			}
			if (ans <= limit) {
				x = mid;
				left = mid + 1;
			}
			else {
				right = mid - 1;
			}
		}
		cout << x;
	}
}