[baekjoon 3079] 입국심사 (매개변수탐색, 이분탐색) (C++)

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

3079번: 입국심사

심사대의 개수와 심사를 할 사람 수가 주어진다.

각 심사대에서 걸릴 수 있는 시간은 최대 10^9이고, 총 10만 개가 있다.

 

매개 변수 탐색을 통해서 우리가 찾으려는 값은 최종 걸리는 시간이다.

 

만약 자리가 1 2 3 4 5가 있고, 최종 걸리는 시간이 10이라고 가정한 상황이면 총 10의 시간 동안 몇 명이 앉을 수 있을까?

 

1의 자리에 10명, 2의 자리에 5명, 3의 자리에 3명, 4의 자리에 2명, 5의 자리에 2명이 앉을 수 있다.

즉, 최종 걸리는 시간을 각 자리의 사용량으로 나눈 몫이 앉을 수 있는 사람의 수가 된다.

 

따라서, 이분 탐색하듯이 start와 end를 정하고, mid값을 조정해주면서 걸리는 시간을 찾는 문제가 되겠다.

사람 수가 목표보다 적으면 당연히 최종 걸리는 시간을 늘려줘야 하겠고(start = mid + 1), 목표보다 충분히 많이 앉을 수 있으면 타이트하게 시간을 줄여줘야 한다.(end = mid - 1)

 

참고로 long long의 범위에서 경곗값을 정하는 게 어려웠는데, 사람의 수 * 걸리는 시간 중 최댓값으로 해주었다.

만약 경곗값을 long long의 끝인 10^18으로 할 경우, 제일 처음에 mid값을 구할 때 start + end에서 오버플로우가 나올 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
ll N, M,num;
vector<int> v;
// 매개변수 탐색으로 최종 시간을 각 대기열의 사용량을 이용해서 구한다.
// 최종시간 / 사용량하면 시간 동안 그 자리에 몇 명이 앉을 수 있는지 사람 수를 구할 수 있다.
int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());

	ll start = 1, end =v.back() * M;

	while (start <= end) {
		ll mid = (start + end) / 2;
		ll cnt = 0;

		for (int i = 0; i < v.size(); i++) {
			cnt += mid / v[i];
			if (cnt > M)
				break;
		}

		if (cnt >= M) { // 충분하므로 시간을 줄여야한다.
			end = mid - 1;
		}
		else {
			start = mid + 1;
		}
	}
	cout << start;
}