[2512] 예산

---

알고리즘 분류가 이분 탐색으로 되어있다.

 

일단 상한액의 범위는 (1 ~ INPUT의 최댓값)이다.

이를 이분 탐색 해나가며 상한액을 최댓값으로 갱신한다.

 

상한액이 만약 key라면, key를 기준으로 전체 예산을 구해본다.

이 총 예산액이 M보다 크다면 key를 너무 크게 잡은 것이므로 더 작게 잡고 이분탐색을 진행한다.

총 예산액이 M보다 작거나 같다면 이 key가 최댓값인지 따져보고, 더 큰 상한액을 위해 이분탐색을 진행한다.

 

자세한 설명은 코드에 적어놓았다.

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

int N;
int INPUT[10000];
int M;
int maximum = -1;

void BinarySearch(int start, int end, int key) {

	if (start > end) { // 다 탐색했으면
		return;
	}
	key = (start + end) / 2; // 상한액으로 잡음

	// key가 상한액인 경우의 총 예산액을 구해봄
	int s = 0;
	for (int i = 0; i < N; i++)
	{
		if (INPUT[i] > key) {
			s += key;
		}
		else {
			s += INPUT[i];
		}
	}

	if (s > M) { // 상한액 오류, 더 작게 잡음
		BinarySearch(start, key - 1, key);
	}
	else { 
		if (key > maximum)maximum = key; // 새로 잡은 상한액이 기존보다 크면 갱신
		BinarySearch(key+1, end, key); // 상한액이 더 커질 수 있는지 더 크게 잡아봄
	}

	
}

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

	int sum = 0;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> INPUT[i];
		sum += INPUT[i];
	}
	cin >> M;
	
	sort(INPUT, INPUT + N); // 이분 탐색을 위해 정렬
	

	if (sum > M) { // 예산 초과 시
		BinarySearch(1, INPUT[N - 1],-1);

		cout << maximum;
	}
	else { // 예산이 남아돌면
		cout << INPUT[N - 1]; // 각 지역 중 최댓값 출력
	}
}