[Codeup] 4766. 예산

1. 문제 링크

https://codeup.kr/problem.php?id=4766

코드업

 

2. 문제 풀이

N이 최대 10,000이고, 예산 요청 액의 최대 값은 100,000으로 모든 경우를 다 돌게 되면, O(N * 100,000)이 된다. 

즉, 이 문제에서는 시간초과가 발생한다.

 

따라서, 모든 상한액을 순차적으로 확인하기보다 가능한 상한액과 불가능한 상한액의 경계를 찾아내야한다.

 

각 국가에 배정되는 상환액을 x라고 잡아서 총 배정액을 계산한다.

이때, 상환액 이하의 예산요청은 요청한 금액 그대로 배정한다.

 

총 배정액을 계산했을때 M 이하라면, 그 이하의 상환액은 배정 가능하다.

총 배정액을 계산했을때 M을 초과하면, 그 이상의 상환액은 배정 불가능하다.

 

이때, 이분 탐색으로 상환액의 범위를 잡으면, 계산의 횟수를 크게 줄일 수 있다.

 

3. 아이디어

1. 문제에서 구해야 하는 상환액의 범위는 1~지방 예상 요청 액 중 최대값으로 한다.
2. 이 둘 사이의 중간 값을 계산하여, 예산 요청액의 합을 계산한다.
3. 이 합이 M을 넘으면, 해당 상한액으로는 배정이 불가능하고, 이보다 큰 상한액도 후보에서 제외된다.
4. 반면, M보다 작거나 같으면, 해당 상환액으로 배정이 가능하여, 이보다 작은 상한액도 후보에서 제외된다.
5. 이분 탐색 형태로 탐색을 진행해서 left(최소 범위)가 right(최대 범위)를 넘기 전까지 반복한다.

 

4. 구현

※ C++ Source Code

#include <iostream>
#include <algorithm>
using namespace std;
int n;
int region_budget[10005];
int m;
int max_value = 0;
bool CanBudget(int budget)
{
	int sum = 0;
	for (int i = 0; i < n; i++)
	{
		sum += min(region_budget[i], budget); 
	}

	if (sum > m) // m보다 크면 해당 상환액으로 배정 불가능
	{
		return false;
	}
	else // m보다 작으면 해당 상환액 배정가능
	{
		return true;
	}
}
int main(void)
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> region_budget[i];
		if (max_value < region_budget[i]) max_value = region_budget[i];
	}
	cin >> m;

	int left = 0;
	int right = max_value;
	int ans = 0;

	while (left <= right)
	{
		int mid = (left + right) / 2;
		if (CanBudget(mid)) // 만들 수 있으면, 해당 값보다 큰 경우 탐색
		{
			ans = mid;
			left = mid + 1;
		}
		else // 만들 수 없으면 해당 값보다 작은 범위 탐색
		{
			right = mid-1;
		}
	}
	cout << ans;

}