BOJ - 2512번 예산(C++)

문제 출처: https://www.acmicpc.net/problem/2512

문제 난이도

Sliver 3

문제 접근법

이분 탐색을 이용하는 문제.
혹시 감이 잡히지 않는 사람들이라면 다른 사람 코드 보기 전에, 이분 탐색을 공부하고 다시 문제를 풀어보길 추천한다.

통과 코드

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


using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, total, minV=0, maxV=-1;
	vector<int> contry;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		contry.push_back(x);
		maxV = max(maxV, x);
	}
	cin >> total;
	while (minV <= maxV) {
		int mid = (minV + maxV) / 2;
		int tmp = 0;
		for (int i = 0; i < contry.size(); i++) {
			if (contry[i] <= mid) {
				tmp += contry[i];
			}
			else {
				tmp += mid;
			}
		}
		if (tmp > total) {
			maxV = mid - 1;
		}
		else {
			minV = mid + 1;
		}
	}

	cout << maxV << "\n";
	return 0;
}