Koala - 2기/B반

[2512번] 예산

kyc5644 2021. 2. 9. 00:31

 

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

 

2512번: 예산

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

www.acmicpc.net

 

- 2512 예산 문제 설명 -
- 2512번 예산 중요 코드 -

 

 

전체 코드

 

더보기 
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 10000;
int N, M;
int num[MAX];

bool calc(int mid) {
	int sum = 0;
	for (int i = 0; i < N; i++)
		sum += min(num[i], mid);

	if (sum <= M)
		return true;
	return false;
}

int main() {
	int right = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
		right = max(right, num[i]);
	}
	cin >> M;

	int ans = 0, left = 1;
	for (int i = 0; i < M; i++) {
		while (left <= right) {
			int mid = (left + right) / 2;
			if (calc(mid)) {
				ans = mid;
				left = mid + 1;
			}
			else right = mid - 1;
		}
	}
	cout << ans;
}