본문 바로가기
Problem Solving/백준

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

by kadokok 2023. 4. 16.

  문제  

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

 

3079번: 입국심사

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

www.acmicpc.net


  풀이  

  • 사용 알고리즘 : 파라메트릭 서치
  • 시간 복잡도 : $O(N * log(M * min(T_{k})))$

파라메트릭 서치로 풀 수 있는 문제였습니다.

 

이 문제에서의 큰 문제점은 $M$의 상한이 $10^{9}$이라는 점입니다. 완전 탐색 시 발생하는 시간은 대략 $O(N^{M})$ 정도일 테고, 당연히 터집니다. $M$의 상한이 너무 크니, 이를 로그 시간으로 최적화시킬 필요가 있습니다.

 

생각해 볼 수 있는 접근은, 심사를 받는 데 걸리는 시간의 최솟값이 얼마인가? 라는 최적화 관점에서, 임의의 심사 시간 $x$에 대하여 $M$명의 사람들을 모두 심사하는 데 $x$ 시간 안에 가능한가? 라는 결정 문제 관점으로 바꾸어 생각해 보는 겁니다.

만약 $x$ 시간안에 가능했다면, $x$보다 더 최소의 시간을 찾아 심사가 가능한지 아닌지 여부를 반복해서 확인해 주면 되겠죠.

 

이때 임의의 심사 시간 $x$는 이분 탐색을 이용하여 정할 수 있습니다.

가능한 심사 시간의 하한 $low$와 상한 $high$ 범위를 설정해주고, 범위 사이의 수 $x$를 임의대로 지정해 줍니다. 그리고 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단해 주는데, 만약 심사가 가능했다면 기존의 심사 시간 $x$ 값을 더 낮춰서 시도해볼만하겠죠. 따라서 이 경우에는 따져봐야 할 범위가 기존의 범위 $[low, high]$에서 범위 $[low, x - 1]$ 로 줄어들게 됩니다.

만약 심사가 불가능했다면 기존의 심사 시간 $x$ 값을 더 높여서 다시 시도해야 합니다. 따라서 이 경우에는 따져봐야 할 범위가 기존의 범위 $[low, high]$에서 범위 $[x + 1, high]$ 로 줄어들게 됩니다.

이러한 흐름은 이분 탐색의 로직과 똑같습니다. $M$명의 사람들 모두 심사 가능한 최소의 $x$ 시간을 이분 탐색으로 찾아주는 거죠.

 

그렇다면 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단은 어떻게 할 수 있을까요?

최대한 그리디 하게 생각해 주면 되는데, $x$ 시간 동안 각 심사대를 한 번도 비우지 않고 최대로 사람을 심사했을 때 총 몇 명을 심사할 수 있는지 세주기만 하면 됩니다.

이는 총 심사 시간 $x$를 심사대에서 심사하는 데 걸리는 시간 $T_{k}$로 나눴을 때의 몫을 취해 더해주면 되겠죠.

예를 들어, 총 심사 시간이 30이라 했을 때 심사대 A에서 걸리는 시간이 7이라면, 심사대 A에서 최대로 심사할 수 있는 사람의 수는 4명이 되는 식입니다.

이런 식으로 총 심사 시간 $x$에 대해서 $T_{k}$로 나눈 모든 몫을 다 더해준 값이 $sum$이라고 했을 때,  $sum \geq M$ 이라면 $x$ 시간 안에 $M$명 모두 심사 가능하다는 뜻이 되고, $sum < M$ 이라면 $x$ 시간 안에 $M$명을 심사할 수 없다는 뜻이 됩니다.

 

이제 아이디어는 다 정리해 봤으니, 시간 복잡도 분석을 해봅시다.

먼저 가능한 심사 시간의 범위부터 대략적으로 따져보면, 하한은 1이 될 거고 상한은 $M * min(T_{k})$가 될 겁니다. 그렇다면 저 범위 안에서 최소의 시간을 찾는 데 걸리는 시간은 이분 탐색을 사용하니 $O(log(M * min(T_{k})))$ 정도가 되겠죠.

또한, 심사 시간 $x$에 대해 $M$명의 사람들이 모두 심사 가능한지 판단하는 시간은 입국 심사대의 수만큼 들 테니 $O(N)$이 될 것이니, 이 문제는 $O(N * log(M * min(T_{k})))$ 시간 안에 해결할 수 있습니다.

 

마지막으로 주의해야 할 점은, $T_{k}$의 상한이 상당히 커서 중간 연산 과정에서 오버플로우가 발생할 확률이 있습니다. 이 부분만 주의해서 코드 작성하시면 맞왜틀은 피하실 수 있을 겁니다..(경험담)


  코드  

#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
const int inf = 2e9;
const int SIZE = 1 << 18;
const int MOD = 1e9 + 7;

int main(void){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m;
	cin >> n >> m;
	vector<int> v;
	int minn = inf;
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		v.push_back(k);
		minn = min(minn, k);
	}
	ll lo = 1;
	ll hi = (ll) minn * m;
	ll mid;
	int vSize = v.size();
	ll ans = INF;
	while (lo <= hi) {
		mid = (lo + hi) >> 1; // 심사하는데 걸린 총 시간
		ll cnt = 0; // 심사받을 수 있는 최대 인원 수
		for (int i = 0; i < vSize; i++) {
			cnt += mid / v[i];
		}
		if (cnt >= m) {
			ans = min(ans, mid);
			hi = mid - 1;
		}
		else {
			lo = mid + 1;
		}
	}
	cout << ans;
	return 0;
}

댓글