[BOJ/C++] 2512 예산

문제

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

풀이

처음에 vector에서 값 빼내며 최대 예산 구하는 방식으로 풀었는데 시간초과..! 이분 탐색 문제였다.

여태까지는 코테 문제를 보면 거의 무조건 빡구현으로 풀었는데 이제 어떨 때 어떤 알고리즘을 왜 사용하는지 조금 보이기 시작했다. 감 잃지 말고 꾸준히 화이팅하자💪🏻

ex) 110 120 140 150
0~150 탐색 (mid=75) ➡️
76~150 탐색 (mid=113) ➡️
114~150 탐색 (mid=132) ⬅️
114~131 탐색 (mid=122) ➡️
123~131 탐색 (mid=127) ➡️
128~131 탐색 (mid=129) ⬅️
128~128 탐색 (mid=128) ⏸️
ans=127

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> v;
	int N, MAX;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	cin >> MAX;
	sort(v.begin(), v.end());
	
	int start = 0;
	int mid = 0;
	int end = v.back();
	int sum = 0;

	while (start <= end) {
		sum = 0;
		mid = (start + end) / 2;
		for (int i = 0; i < N; i++) {
			sum += min(v[i], mid);
		}

		if (MAX >= sum) {
			start = ++mid;
		}
		else {
			end = --mid;
		}
	}

	cout << end;

	return 0;
}