[백준 14575] 뒤풀이 (C++)

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

문제

---

도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.

하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수밖에 없었다.

도현이는 우선 각 사람에게 어느 정도 마시면 기분이 좋은지(Li)와, 어느 정도 마시면 힘든지(Ri)를 물어보았다. 각 사람은 Li미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri를 초과하는 술을 마시면 천국으로 가버릴 수도 있다. 도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.

그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다. 마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어 있었고, 도현이는 정확히 T의 술을 결제하였다.

이제 도현이는 모든 사람 i에게 Li이상 Ri이하의 술을 주면서, 그 총합이 정확히 T가 되도록 술을 분배하려고 한다. 하지만 안타깝게도, 사람들은 자신의 주량을 과대평가하는 경향이 있다. 이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다. 이제 도현이는 술도 결제했고, 주량도 조사했으므로,

1. 모든 사람 i가 Li이상 Ri이하의 술을 받으면서,
2. 모든 사람이 받은 술의 총합이 정확히 T가 되고,
3. 어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는,

그러한 S값만 결정하면 된다.

도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.

만약 그런 값이 여러 개라면, 도현이는 그 중 가장 작은 값을 찾고 싶다.

입력

---

 첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 ≤ N ≤ 1000, 1 ≤ T ≤ 109)

둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li와 Ri값이 주어진다. (1 ≤ Li ≤ Ri ≤ 106)

 

출력

---

만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1만을 출력한다.

문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

 

문제 풀이

---

이분탐색 문제.

 

사람마다 마셔야 하는 최소양이 있다. 이 양을 모두 더했을 때 T보다 크다면 술의 총량이 부족해 모두가 최소 양을 만족시키지 못한다. 따라서 -1을 출력한다. 또한 사람마다 마실 수 있는 최대 양도 존재한다. 이 양을 모두 더했을 때 T보다 작다면 모든 사람이 아무리 마셔도 T를 충족하지 못하므로 -1을 출력한다.

술은 한 사람당 S 이하만 주어야 하므로 S의 최솟값은 Li의 최댓값이 된다. 이제 이분 탐색을 통해 S의 적절한 값을 찾는다. 각 사람에게 줄 수 있는 술의 최대 양은 Ri와 S중 더 작은 값이다. 이 최댓값을 모두 더했을 때 T보다 작다면 S가 작다는 뜻이므로 left = mid+1을 통해 S의 값을 키울 수 있게 한다. 최댓값을 모두 더했을 때 T보다 크거나 같다면 술의 양을 적당히 조절해 술의 양을 정확히 T로 맞출 수 있다. 따라서 이 값이 정답 중 하나가 될 수 있고, right = mid-1을 통해 S의 양을 줄여 더 작은 S값이 있는지 찾아주면 된다.

 

아래는 코드.

#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
long long N, T;

pair<long long, long long>* arr;
long long answer = 987654321;
void binarySearch(long long start, long long end)
{
	long long left = start;
	long long right = end;
	while (left <= right)
	{
		long long mid = (left + right) / 2;
		long long maxValue = 0;
		for (int i = 0; i < N; i++)
		{
			maxValue += min(arr[i].second, mid);
		}
		if (maxValue < T)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
			answer = min(answer, mid);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	cin >> N >> T;
	arr = new pair<long long, long long>[N];
	long long minSum = 0;
	long long maxSum = 0;
	long long maxOfMin = 0;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i].first >> arr[i].second;
		minSum += arr[i].first;
		maxSum += arr[i].second;
		maxOfMin = max(maxOfMin, arr[i].first);
	}
	sort(arr, arr + N);
	if (minSum > T || maxSum < T)
	{
		cout << -1 << "\n";
	}
	else
	{
		binarySearch(maxOfMin, 1000000000);
		cout << answer << "\n";
	}
	return 0;
}