문제 출처

1. 문제설명

  • 요청한 금액이 주어진다.
  • 요청한 금액에서 최대한 예산을 취하고자 한다.
  • 모든 요청이 배정될 수 있는 경우 요청한 금액을 그대로 배정
  • 아니라면, 특정한 정수 상한액을 계싼하여 그 이상인 예싼 요청에는 모두 상한액을 배정
  • 합이 최대가 되는 상한액을 구하라!



2. 알고리즘 설계

  • 어떤 값을 찾아야 한다..? ==> 이분 탐색
  • 어떤 값을 left, right로 지정할지가 관건인 문제이다.
  • left는 0, right는 정렬된 값 중 가장 큰 값으로 지정한다.



3. 로직

  • 이분 탐색은 오름차순 정렬이 전제조건이다.
  • 위에서 언급한 것처럼 left, right를 지정하고,
  • mid는 (left+right) / 2 한다.
  • 총액을 더해준다.
    • mid 값이 현재 예산보다 적다면, mid
    • 아니라면, 현재 예산을 더한다.
  • 총액이 총 예산 m과 같아지면 mid 값 반환
    • 총액이 총 예산보다 크면, right 값을 mid-1
    • 총액이 총 예산보다 작으면, left 값을 mid+1
  • 정확히 구하지 못하면 상한액을 배정하므로, 현재의 총액이 m보다 작으면 반환 값을 갱신한다.



4. 전체 코드

#include<bits/stdc++.h>
#include <unordered_map>
using namespace std;

vector<int> v;
int n, m;

int binary_search() {
	sort(v.begin(), v.end());

	int left = 0, right = v[n - 1];
	int ret = 0;

	while (left <= right) {
		int mid = (left + right) / 2;
		int sum = 0;
		for (int i = 0; i < v.size(); i++) {
			if (mid < v[i]) sum += mid;
			else sum += v[i];
		}

		if (sum == m) return mid;
		if (sum > m) right = mid - 1;
		else left = mid + 1;

		if (sum < m) ret = max(ret, mid);
	}
	return ret;
}

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

	cin >> n;
	for (int tmp, i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}
	cin >> m;

	cout << binary_search();
	return 0;
}