[백준/알고리즘] 2512번 예산 (실버 3)

클릭하면 백준 페이지로 이동합니다.

---

 

BOJ 2512번

 

지역의 개수 n이 주어진다. 이후 n개의 지역에서 요청한 예산이 입력된다. 마지막으로 국가예산의 총액 m이 주어졌을 때, 예산의 상한을 출력하여라.

 

풀이 알고리즘 : 이분탐색

 

전형적인 이분탐색 문제이다. 생각할 점은 두 가지이다.

 

첫번째는, 상한선을 기준으로 이분탐색을 돌리는 것이다.

두번째는, 각각의 이분탐색에서, 총액을 구하고, 총액에 따라 범위를 재설정하는 것이다.

 

이분탐색 결과 m보다 현재 탐색한 총액이 크다면, 상한선이 너무 높은것이고,

m보다 현재 탐색한 총액이 작거나 같다면, 답이 될 수 있으며, 더 높은 상한선이 존재 할 수 있다.

 

소스코드 보기

 

#include <bits/stdc++.h>
// 2의 제곱수 판정
#define POW2(X) (X) == ((X)&(-(X)))

// 기본설정
typedef long long ll;
using namespace std;

int main(void) {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int n, m, ans;
	cin >> n;
	int needs[n] = {0};
	for(int i = 0; i < n; i++) cin >> needs[i];
	sort(needs, needs + n);
	cin >> m;
	int le = 0, ri = needs[n - 1];
	while(le <= ri) {
		int mid = (le + ri) / 2;
		int cur = 0;

		for(int i = 0; i < n; i++) {
			if(needs[i] <= mid) {
				cur += needs[i];
			} else {
				cur += mid;
			}
		}

		if(cur <= m) {
			ans = mid;
			le = mid + 1;
		} else {
			ri = mid - 1;
		}
	}
	cout << ans;
	return 0;
}