백준 3079번 입국심사(C++)

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

3079번: 입국심사

 

처음 문제를 봤을 때 우선순위큐 문제라고 생각했다.

그러나 몇 초 쉬고 다른 심사대로 이동하는 것을 생각해보면 아무래도 우선순위 큐로는 풀어낼 수 없다. 그러다가 분류를 보니 이분탐색 파라메트리 서치가 보였다.

 

 ? 아니 이걸 어떻게 파라메트리로 ?

 

라고 생각해서 기다렸다가 가는 시간초를 파라메트릭으로 판단하나? 생각했는데 그걸리가 없지. 파라메트릭은 보통 "정답" 을 반환한다.

 

answer = mid 를 갱신해나가는 식이다.

그러므로 여기서 mid값은 "걸리는 시간" 이다. 

그리고 이 시간동안 최대 몇명의 인원을 심사할 수 있느냐? 하는 개수는 mid / A심사대의 시간 + mid / B심사대의 시간 ... 이다. 그렇다면 시간복잡도는

 

O(NlogN) 으로 풀어낼 수 있다.

 

파라메트릭이라는 것을 파악하는것과 각 시간동안 몇 명의 심사를 볼 수 있는가를 알아내는 능력이 중요했다. 이것을 파악하면 이분탐색을 구현하는 것은 어렵지 않다. 그리고 파라메트릭을 할 때는 그냥 맘편하게 전부 long long 박아버리는게 마음 편하다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;
int N, M;
vector<long long> vec;
bool check(long long num) {
	long long sum = 0;
	for (auto a : vec){
		sum = sum + num / a;
	if (sum >= M)
		return true;
    }
		return false;
}

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);

	cin >> N >> M;

	long long max_num = 0;

	for (int i = 0; i < N; i++) {
		long long tmp;
		cin >> tmp;
		vec.push_back(tmp);
		max_num = max(max_num, tmp);
	}

	long long hi = max_num * M;
	long long lo = 0;
	long long answer = max_num * M;
	while (lo + 1 < hi) {
		long long mid = (hi + lo) / 2;
		//cout << mid << endl;
		if (check(mid)) {
			answer = mid;
			hi = mid;
		}
		else {
			lo = mid;
		}
	}

	cout << answer << '\n';
}