[백준 2512] 예산

배정가능한 예산 중 최대값을 찾는 것이므로 이분탐색으로 해결 가능

 

이분탐색하는 binarysearch함수는 left<=right 를 만족하면 계속 돈다

 

즉 마지막으로 while문을 도는게 left==right 일때이고 이 이후에는 무조건 left > right이 된다

 

그림을 그려보면

 

---

 

#include <iostream>
#include <algorithm>
#define SIZE 10000

using namespace std;

int arr[SIZE];
int N,M;

// 이 함수는 최적의 최대값을 찾기 위해 동작함
// 즉 left <= right 일때 계속 돌아가서 
// left==right일때 끝남
// 근데 left==right일때 만족을 할 수도 있고 안할 수도 있음
// 그래서 그 전 값을 계속 저장해놔야함

int binarysearch(int left, int right) {
	int prev = 0;
	
	while (left <= right) {
		int mid = (left + right) / 2;
		int sum = 0;

		for (int i = 0; i < N; i++) {
			if (arr[i] > mid) sum += mid;
			else sum += arr[i];
		}

		// sum값 줄이기
		if (sum > M) { right = mid - 1;}
		// sum값 늘리기
		else if (sum < M) { left = mid + 1; prev = mid; }
		else { prev = mid; break; }
	}
	return prev;
}

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

	cin >> N;
	int max = 0;
	
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
		if (arr[i] > max) max = arr[i];
	}
	cin >> M;

	cout << binarysearch(0, max);
	return 0;
}