[C++] 백준 2512번 예산

이분탐색으로 문제를 해결했습니다.

예산의 상한선을 지정해서 예산과 최대한 비슷하게 만드는 문제입니다.

1부터 N까지의 수를 전부 계산하면 시간초과가 발생하게 됩니다.
그래서 sort를 해준 다음 이분탐색을 통해서
반틈씩 이동하면서 가장 가까워지는 값을 찾아냈습니다.

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

typedef long long ll;

int n;
int result = 0;
ll sum = 0;
ll budget;
ll leftN, rightN;
ll arr[10001];

void binary_find(ll x)
{
	ll temp = 0;

	if (leftN > rightN) {
		return;
	}

	for (int i = 0; i < n; ++i) {
		if (arr[i] > x) {
			temp += x;
		}
		else {
			temp += arr[i];
		}

		if (budget < temp) {
			rightN = x - 1;
			binary_find((rightN + leftN) / 2);
			return;
		}
	}

	if (sum < temp) {
		sum = temp;
		result = x;
	}

	leftN = x + 1;
	binary_find((rightN + leftN) / 2);
}

int main(int argc, char *argv[]) 
{
	scanf("%lld", &n);

	memset(arr, 0, sizeof(arr));

	for (int i = 0; i < n; ++i) {
		scanf("%lld", &arr[i]);
	}
	sort(arr, arr + n);

	scanf("%lld", &budget);

	leftN = 0;
	rightN = arr[n - 1];

	binary_find((leftN + rightN) / 2);

	printf("%d\n", result);

	return 0;
}