[BOJ 2512] 예산

문제

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

임의의 정수 N개(예산요청)와 그 정수들의 합의 상한(총 예산) M이 주어졌을 때, 정수들의 합이 최대가 되도록 특정한 정수 X를 구하는 문제다. 단, 조건은 다음과 같다.
1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.
2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.
이때, 1번의 경우에는 X가 아닌 주어진 정수들의 최댓값을 출력한다.

예를 들어, 4개의 정수 120, 110, 140, 150과 485이 상한으로 주어졌다면, 120+110+140+150 > 485 이고 각각의 수를 120, 110, 127, 127로 배정하면 그 합이 484로 가능한 최대가 되므로 X는 127이 된다.

풀이과정

이분 탐색 알고리즘을 선택하였다.

1. 정렬
   • 입력받은 정수들을 오름차순으로 정렬한다.
2. value로 탐색할지 index로 탐색할지 결정
   • value로 탐색한다.
3. 첫 탐색의 시작과 끝을 설정
   • start = 0
   • end = 정렬한 정수들 중 N-1번째 수
4. 비교할 기준을 정해 탐색을 반복
   • 비교할 기준으로 sum 변수를 생성해 min(mid, n번째 수)을 누적해 더한다.
   • sum과 M을 비교해 X를 설정하고 start와 end를 설정해주고 재탐색한다.

코드

https://github.com/meraki6512/Algorithm/blob/master/AlgorithmProject1/BOJ2512.cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;
vector<int> n;

int binary_search() {

	int start = 0;
	int end = n[N-1]; //max
	int mid;

	int sum, ret;

	while (start<=end) {
		mid = (start + end) / 2;
		
		sum = 0;
		for (int i = 0; i < N; i++) {
			sum += min(mid, n[i]);	
		}
		
		if (sum <= M) {
			ret = mid;
			start = mid + 1;
		}
		else {
			end = mid - 1;
		}
	}

	return ret;
}

int main() {

	cin >> N;

	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		n.push_back(x);
	}

	cin >> M;

	sort(n.begin(), n.end());
	
	cout << binary_search();

}