백준 알고리즘 2512번 문제 : 예산

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

2512번: 예산

 

binary search를 이용한 문제입니다!

 

문제 분석

국가예산을 여러 지방에 분배하려 한다. 모든 예산요청을 배정해 주기는 어렵다. 정해진 총액 이하에서 가능한 한 최대의 총 예산을 배정하려 한다. 가능한 최대로 분배할 수 있는 예산의 금액은?

 

1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정한다.

2. 모든 요청이 배정될 수 없는 경우에는 특수한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정한다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정한다.

 

지방의 수 N, 각 지방의 예산 요청을 표현하는 N개의 정수 및 총 예산을 나타내는 정수 M이 주어진다.

다루는 수의 범위가 10^9까지 크다는 점도 염두해두시면 좋을것 같습니다!

 

문제 해결

최대로 분배할 수 있는 예산의 금액을 구하는 문제네요!

 

알고리즘은 간단하지만 상당히 까다로운 문제입니다.

 

먼저 주어진 총예산을 배정하려면 총 예산액수에서 배정할 지역의 수를 나눠야합니다.

 

한 지역이 받는 예상 배정액 = M / N; 

 

그리고 조건 1번 2번을 통해 모든 요청이 배정 될 수 있는지 없는지를 알아야겠죠?

 

이때 이분 탐색을 이용해서 요청한 모든 금액을 배정받을 수 있는 지역들과 요청한 금액에 미달되는 금액을 배정받는 지역들을 구분합니다.

 

이분 탐색을 수행하기 위해서는 배열들이 모두 정렬되어있어야하는데요!

 

저는 오름 차순으로 quick 정렬을 했습니다.

 

문제의 예제를 예로 들면

key	1	2	3	4
value	110	120	140	150

M = 485 이니까 처음 binary search 할 예상 배정액은 121입니다.

 

121은 키값 2와 3 사이에 있네요~

 

the rightmost element를 찾는 binary search를 사용하면 예산을 121씩 지역들에 분배했을때

 

분배가 가능한 지역은 1,2번 지역이 되고, 요청한 액수보다 부족한 지역은 3,4번 지역이 됩니다.

 

그런데 조건 1에 의해 110을 요청한 지역에 예산 121만큼 다 줄 필요는 없어요!

 

초과한 액수 11 ( 지역 1 ), 1 ( 지역 2 )를 회수해서 분배하지 못한 3번 4번 지역에 다시 분배합니다.

 

121 + (11 + 1)/2 = 127

 

key	1	2	3	4
value	110	120	140	150

 

또 다시 이분 탐색을 이용해 완전히 분배한 지역과 덜 분배받은 지역을 구분해봅니다!

 

127만큼의 예산으로는 각 지역의 예산요청을 만족시키기가 턱없이 부족하네요.

 

분배해줄 예산이 없으므로 127이 정답이 됩니다!

 

소스코드

#include <iostream>
#include <vector>

using namespace std;
vector<long long> N;

void quick(int low, int high);
int partition(int low, int high);
int binary(int val, int low, int high);

int main() {
	long long budget, m, margin, tm;
	int n, del, pdel;

	cin >> n;
	N.resize(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> N[i];
	}
	quick(1, n);
	cin >> budget;
	m = budget / n;
	budget -= m * n;
	pdel = 0;
	while (true) {
		del = binary(m, pdel, n);
		if (del == pdel) {
			if (N[n] < m) {
				m = N[n];
			}
			break;
		}
		margin = 0;
		for (int i = pdel + 1; i <= del; i++) {
			margin += (m - N[i]);
		}
		if (n - del != 0) {
			m += (tm = (budget + margin) / (n - del));
			budget+=(margin - tm * (n - del));
		}
		else {
			m = N[n];
			break;
		}
		pdel = del;
	}
	
	cout << m;
}

int binary(int val, int low, int high) {
	int mid = (low + high) / 2;
	if (low >= high) {
		return high;
	}

	if (N[mid] == val) {
		return mid;
	}else if (N[mid] < val) {
		binary(val, mid, high);
	}
	else {
		binary(val, low, mid - 1);
	}
}

void quick(int low, int high) {
	int mid;
	if (low > high) {
		return;
	}
	mid = partition(low, high);
	quick(low, mid - 1);
	quick(mid + 1, high);
}

int partition(int low, int high) {
	int pivot, i;
	long long pivotItem, temp;

	pivot = i = low;
	pivotItem= N[pivot];
	for (int j = low + 1; j <=high; j++) {
		if (pivotItem > N[j]) {
			temp = N[++i];
			N[i] = N[j];
			N[j] = temp;
		}
	}
	N[pivot] = N[i];
	N[i] = pivotItem;
	return i;
}