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

이분 탐색을 이용하여 풀면 된다. 

 

1. 벡터 V에 값을 저장 후 오름차순으로 정렬

2. high 값은 벡터의 제일 큰 원소의 값으로 저장

3. sum 변수에 mid값과 벡터의 원소의 값을 비교하여 작은값을 더함

4. sum값이 m보다 크거나 같으면 result 값에 mid 값 저장 후 이분 탐색

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll; 

int main() {
	ios::sync_with_stdio(false); 
	cin.tie(0); cout.tie(0); 
	int n; cin >> n; 
	vector <ll> v; 
	ll s, e; 

	for (int i = 0; i < n; i++) {
		ll a; cin >> a; 
		v.push_back(a); 
	}
	sort(v.begin(), v.end()); 
	ll m; cin >> m; 
	ll l = 0; 
	ll h = v[n-1]; 
	ll result = 0; 
	while (l <= h) {
		ll mid = (l + h) / 2; 
		ll sum = 0; 
		for (int i = 0; i < n; i++) {
			sum += min(v[i], mid); 
		}
		if (m >= sum) {
			result = mid;
			l = mid + 1;
		}
		else h = mid - 1; 
	}
	cout << result; 
}

 

2512번: 예산