백준 2512번 예산(C++)

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

2512번: 예산

 어려운 문제는 아니지만 파라메트릭의 입문용으로 괜찮은 문제라고 본다. 

먼저 이 문제는 hi, lo를 설정하는 것이 간편하다 반드시 가장 큰 cost를 갖는 도시의 예산을 넘을 수 없다. 그러므로 hi 는 가장 큰 예산으로 low 는 0으로 잡고 이분탐색을 진행한다.

 

체킹같은 경우는 만약 지금 분배 예산이 도시의 예산을 넘는다면 도시의 예산을, 그렇지 않다면 분배 예산을 더하여 마지막 총 액수와 비교하면 된다. 

 

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

int N;
vector<long long> citis;
long long allasset;

bool check(long long num) {
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		if (citis[i] > num) sum += num;
		else sum += citis[i];
	}
	if (sum > allasset) return false;
	else return true;
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);

	cin >> N;
	long long maxnum  = -1;
	long long firstcheck = 0;
	for (int i = 0; i < N; i++) {
		long long tmp;
		cin >> tmp;
		citis.push_back(tmp);
		firstcheck += tmp;
		maxnum = max(tmp, maxnum);
	}

	cin >> allasset;

	if (firstcheck <= allasset) {
		cout << maxnum << '\n';
		return 0;
	}

	long long hi = maxnum;
	long long lo = 0;
	long long answer = 0;
	while (hi >= lo) {
		long long mid = (hi + lo) / 2;

		if (check(mid)) {
			lo = mid + 1;
			answer = mid;
			//cout << mid << endl;
		}
		else {
			hi = mid - 1;
		}
	}

	cout << answer << '\n';
}