Little Jay

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

알고리즘/BOJ

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

Jay, Lee 2021. 9. 2. 16:19

이진탐색을 활용하는 문제

생각보다 이진탐색할때 조건을 설정하는 부분이 어려웠다

 

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

long long arr[10001];

int main() {

	int n, sum = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		sum += arr[i];
	}

	int budget;
	cin >> budget;

	sort(arr, arr + n);

	long long low = 0;
	long long high = arr[n - 1];

	if (sum <= budget) {
		cout << arr[n - 1] << '\n';
	}
	else {
		while (low + 1< high) {
			long long mid = (low + high) / 2;
			long long temp_budget = 0;

			for (int i = 0; i < n; i++) {
				if (arr[i] >= mid) {
					temp_budget += mid;
				}
				else
					temp_budget += arr[i];
			}

			if (temp_budget > budget) {
				high = mid;
			}
			else if (temp_budget <= budget) {
				low = mid;
			}
		}
		cout << low << '\n';
	}
	return 0;
}

'알고리즘 > BOJ' 카테고리의 다른 글

[C++] 백준 1110번 - 더하기 사이클  (0) 2021.09.03
[C++] 백준 1789번 - 수들의 합  (0) 2021.09.02
[C++] 백준 5622번 - 다이얼  (0) 2021.09.02
[C++] 백준 1149번 - RGB거리  (0) 2021.08.30
[C++] 백준 6443번 - 애너그램  (0) 2021.08.25
Comments