[백준OJ] 14575번 뒤풀이

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

14575번: 뒤풀이

---

 

풀이

먼저, 각 사람들이 최대주량으로 마셨을때 T보다 작거나, 각 사람들이 최소 주량으로 마셨을때 T보다 크다면, 어떠한 경우에도 정확히 T를 맞출 수 없으니 -1을 출력해준다.

 

위를 통과한다면 이분탐색을 이용하여 문제를 해결한다.

이분탐색을 이용하여 S를 설정해준 뒤, S를 가지고 해당 인원들을 정확히 T만큼 먹일 수 있는지 확인을 한다.

 

자신의 주량범위 안에서, S를 초과하지 않고 정확히 T만큼 먹일 수 있는지 확인을 할 수 있는 방법은, 먼저 모든 인원을 최소량 만큼 먹인다고 가정을 한다. 이떄 자신의 최소 주량을 먹였다면, 각 사람마다 더 마실 수 있는 양이 있을것이다.

 

예를들어 A의 주량이 최소=10, 최대=20이고, S=15라고 했을때, 이사람이 10만큼 마셨다고 가정을 하면, 5만큼을 더 마실수 있다.

B의 주량이 최소=5, 최대 8이고, S는 똑같이 15라고 했을때, 이사람이 5만큼 마셨다고 가정을 하면, 3만큼을 더 마실 수 있다.

 

이렇게 각 사람마다 최소의 술을 먹었을때, 더 먹을 수 있는 술의 양을 모두 더해준다. 이 더 먹을 수 있는 양을 More라고 할때,  More의 양이 현재까지 마시고 남은 술의 양보다 크거나 같다면, 위의 조건을 만족하는 S라고 할 수 있다.

왜냐하면 남은 술을 더 마실 수 있는 사람들에게 나누어 주면, T의 술을 정확히 마시게 할 수 있기 때문이다.

 

 

시간복잡도

이분탐색이므로, O(Nlog(Max(R)) 이 된다.

 

코드

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX	1e9
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

int n, t;
vector<pii> v;

bool can(int s) {
	ll more = 0;
	ll min_sum = 0;
	for (int i = 0; i < n; i++) {
		if (v[i].first > s) {
			return false;
		}
		more += (min(s, v[i].second)-v[i].first);
		min_sum += v[i].first;
	}
	if (more >= t - min_sum) return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> t;
	ll min_sum = 0;
	ll max_sum = 0;
	int left = 0;
	int right = 0;
	for (int i = 0; i < n; i++) {
		int l, r;
		cin >> l >> r;
		min_sum += l;
		max_sum += r;
		right = max(right, r);
		v.push_back({ l,r });
	}
	if (t < min_sum||max_sum<t) {
		cout << -1;
		return 0;
	}
	int answer = MAX;
	while (left <= right) {
		int s = (left + right) / 2;
		if (can(s)) {
			answer = min(answer,s);
			right = s - 1;
		}
		else {
			left = s+1;
		}
	}

	cout << answer;
}