06.02. 예산 [Binary Search & Parametric Search][백준 2512]

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

2512번: 예산

 

Algorithm classification : Binary Search, Parametric Search

 

06.02.1. Problem

One of the roles of the state is to distribute the national budget by examining the budget requests of various provinces. Since the total amount of the national budget is predetermined, it may be difficult to allocate all budget requests. Therefore, the maximum possible total budget is allocated in the following way, below the set total amount.

 

• If all requests can be allocated, the requested amount will be allocated as is.
• If all requests cannot be allocated, a specific integer upper limit is calculated, and all budget requests that exceed the upper limit are allocated. For budget requests below the upper limit, the requested amount will be allocated as it is.

For example, let's say the total national budget is 485 and the budget requests of 4 provinces are 120, 110, 140, and 150, respectively. In this case, if the upper limit is set to 127, 120, 110, 127, and 127 are allocated to the above requests, respectively, and the sum is 484, which is the maximum possible.

Write a program that allocates budgets to satisfy all of the above conditions, given the budget requests of various provinces and the total amount of the national budget.

 

 

06.02.2. Input limit

The first line is given an integer N representing the number of fats. N is 3 or more and 10,000 or less. In the next line, N integers representing each province's budget request are given with spaces in between. All of these values ​​are greater than or equal to 1 and less than or equal to 100,000. The next line is given an integer M representing the total budget. M is N or more and 1,000,000,000 or less.

 

 

06.02.3. Output

The first line prints an integer that is the maximum value among allotted budgets.

 

 

06.02.4. Solution

앞서 소개해드린 나무 자르기 문제와 동일합니다. 총 예산이 M이하가 되게끔하는 상한액을 결정하는 것입니다. 그렇다면 구하고자하는 상한액을 MID로 설정하면 되겠죠.

#include<stdio.h>
#include <algorithm>

using namespace std;

int main(){
	int n, m, i, left = 0, right = 1000000000, mid;
	scanf("%d", &n);
	int a[n], ans = 0;
	
	for(i = 0; i < n; i++){
		scanf("%d", &a[i]);
		ans = max(a[i], ans);
	}
	scanf("%d", &m);
	
	long long temp; 
	while(left <= right){
		mid = (left + right) / 2;
		temp = 0;
		for(i = 0; i < n; i++){
			if(a[i] >= mid){
				temp += mid;
			}
			else{
				temp += a[i];
			}
		}
		
		//printf("%d %d : %d > %d\n", left, right, mid, temp);
		if(temp > m){
			right = mid - 1;
		}
		else{
			left = mid + 1;
		}
	}
	printf("%d", right == 1000000000 ? ans : right);
	
	return 0;
}

최종적으로 RIGHT가 변경되지 않았다면 예산값 중 최댓값을 출력하면 되겠습니다. 물론 RIGHT를 예산값 중 최댓값으로 초기화시켜도 되겠네요. 사실 그러는 편이 더 좋을 것 같습니다.

 

 

아래에 몇 개의 test case를 남겨둘테니 도움되시길 바랍니다.

5
4 4 5 5 2
7
>> 1

3
3 2 4
5
>> 1

3
4 4 5
6
>> 2

2
10 20
12
>> 6

4
101 101 101 101
400
>> 100

4
4 3 2 1
10
>> 4

2
10 1
5
>> 4

10
1 1 1 1 11 11 11 11 11 100
100
>> 41