GitHubSeob

C++ / 백준 / 2512 / 예산 본문

Baekjoon/Silver

C++ / 백준 / 2512 / 예산

GitHubSeob 2021. 8. 20.
문제

 

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

 

2512번: 예산

첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상

www.acmicpc.net

 

 

문제풀이

 

예산을 모두 입력받았을 때, 국가예산을 넘지 않는다면 입력받은 예산 중 가장 큰 값을 출력하면 된다.

이 경우가 아니라면 이분탐색을 통해 값을 구해야 한다.

 

반복문을 통해 입력받은 예산과 상한액 중 작은 값을 sum에 더한다.

sum 값이 국가예산의 총액보다 높으면 상한액을 낮춰야 하므로 right를 줄인다.

sum 값이 국가예산의 총액 이하이면 상한액을 높여도 되므로 left를 늘린다.

 

코드
#include <iostream>
#include <vector>
#define MAX_budget 1e9
using namespace std;

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

	int N(0), M(0);
	int sum(0), max_budget(0);

	cin >> N;
	vector<int>budget(N, 0);

	for (int idx = 0; idx < N; ++idx) {
		cin >> budget[idx];
		sum += budget[idx];
		max_budget = max(max_budget, budget[idx]);
	}
	cin >> M;

	if (sum <= M) {
		cout << max_budget;
	}
	else {
		int left(0), right(MAX_budget);
		while (left <= right) {
			int mid((left + right) / 2);
			int sum(0);
			for (int idx = 0; idx < N; ++idx) {
				sum += min(budget[idx], mid);
			}
			if (sum > M) {
				right = mid - 1;
			}
			else if (sum <= M) {
				left = mid + 1;
			}
		}
		cout << right;
	}
}