C++ / 2512 / 예산 ( 이분 탐색 )

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

문제 요약

국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다.

국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다.

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

예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150이라고 합니다.

이 경우, 상한액을 127로 잡으면, 위의 요청들에 대해서 각각 120, 110, 127, 127을 배정하고 그 합이 484로 가능한 최대가 됩니다. 

여러 지방의 예산요청과 국가예산의 총액이 주어졌을 때, 위의 조건을 모두 만족하도록 예산을 배정하는 프로그램을 작성해야합니다.

문제 풀이

1. 지방의 수를 입력받습니다.

2. 각 지방의 금액을 입력받습니다. 입력받으면서 금액의 총합도 바로 구합니다.

3. 예산의 총액을 입력받습니다. 총액보다 입력받은 금액의 총합이 작으면 입력받은 총액 배열을 정렬하고 가장 큰 값이 된 마지막 인덱스를 출력합니다.

4. 예산의 총액보다 큰 경우 이분탐색 함수를 통해 상한액을 정해야 합니다.

5. 탐색의 시작값으로는 0을 주고 끝값으로는 가장 큰 지방의 금액을 입력합니다.

6. 그 중간 값보다 큰 지방의 금액들은 중간 값으로 더해서 총액을 계산합니다.

7. 예산을 초과 하는 경우는 끝값을 중간값 -1 합니다.

8. 예산을 초과하지 않는 경우는 상한액을 배열에 추가하고 시작 값을 중간 값에 +1 합니다.

9. 시작값이 끝값을 넘어서는 순간 종료합니다.

10. 상한액 배열을 정렬하고 가장 큰 값인 마지막 인덱스를 출력합니다.

주의할 점

최근 이분 탐색 위주로 풀고있는데 간단하게 풀 수 있을 줄 알고 도전한 문제였습니다.

하지만 생각보다 애를 먹었는데,

사용 가능한 상한액중 가장 큰 값을 출력해야 한다는 점 때문이었습니다.

처음엔 이 점을 간과하여 이분 탐색의 mid의 초기값을 가장 작은 금액과 가장 큰 금액을 나눈 값으로 주고

mid를 직접적으로 1씩 감소시키게 하였는데 ( 최대 상한액만 찾아서 리턴 시키고 싶었음 )

이는 주어진 예제에서는 사용 가능한 방법이었지만 다른 예제들에서는 사용하지 못하는 방법이었습니다.

다른 예제는 예제 3번 예제 4번에 적어두었습니다.

 

따라서 정석적인 이분탐색으로 사용가능한 모든 상한액을 배열에 저장하여 정렬하면 가장 마지막 인덱스가 상한액중 가장 큰 값이 된다는걸 눈치채서 해결하였습니다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long int ll;
ll n, m;
ll sum = 0;
vector<int>v;
vector<int> v2;

void bs()
{
	ll start = 0;
	ll end = v[v.size()-1];
	
	while (start <= end)
	{
		ll mid = (start + end) / 2;
		sum = 0;
		for (int i = 0; i < v.size(); i++)
		{
			if (v[i] < mid)
			{
				sum += v[i];
			}
			// 상한액을 넘는 예산은 상한액으로 계산
			else
			{
				sum += mid;
			}
		}
		// 예산 초과하는 경우
		if (sum > m)
		{
			end = mid - 1;
		}
		// 총 금액이 예산 안에 들어가지는 경우
		else if (sum <= m)
		{
			// 예산안에 들어가는 상한액 배열
			// 상한액중에 가장 큰값을 출력해야하기 때문
			start = mid + 1;
			v2.push_back(mid);
		}
	}
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		// 입력받음과 동시에 총 금액 구함
		sum += a;
		v.push_back(a);
	}
	cin >> m;
	sort(v.begin(), v.end());
	// 총 금액이 예산을 넘는 경우
	if (sum > m)
	{
		// 이분탐색
		bs();
		// 상한액 배열을 정렬하면 가장 마지막 값이 상한액중 가장 큰 상한액
		sort(v2.begin(), v2.end());
	}
	// 총 금액이 예산을 넘지 않는 경우는 바로 출력
	else
	{
		// 상한액 출력
		cout << v[v.size() - 1];
		return 0;
	}
	// 상한액 출력
	cout << v2[v2.size() - 1];
	

	return 0;
}

예제 1

4
120 110 140 150
485

결과 1

예제 2

5
70 80 30 40 100
450

결과 2

예제 3

4
101 101 101 101
400

결과 3

예제 4

3
1 3 5
8

결과 4