[백준 3079] 입국심사 (C++)

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

문제

---

상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.

가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다. 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동을 해야 하는 것은 아니다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그 곳으로 가서 심사를 받아도 된다.

상근이와 친구들은 모두 컴퓨터 공학과 학생이기 때문에, 어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될지 궁금해졌다.

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 7초와 10초라고 하자. 줄에 서 있는 사람이 6명이라면, 가장 첫 두 사람은 즉시 심사를 받으러 가게 된다. 7초가 되었을 때, 첫 번째 심사대는 비어있게 되고, 세 번째 사람이 그곳으로 이동해서 심사를 받으면 된다. 10초가 되는 순간, 네 번째 사람이 이곳으로 이동해서 심사를 받으면 되고, 14초가 되었을 때는 다섯 번째 사람이 첫 번째 심사대로 이동해서 심사를 받으면 된다. 20초가 되었을 때, 두 번째 심사대가 비어있게 된다. 하지만, 여섯 번째 사람이 그 곳으로 이동하지 않고, 1초를 더 기다린 다음에 첫 번째 심사대로 이동해서 심사를 받으면, 모든 사람이 심사를 받는데 걸리는 시간이 28초가 된다. 만약, 마지막 사람이 1초를 더 기다리지않고, 첫 번째 심사대로 이동하지 않았다면, 모든 사람이 심사를 받는데 걸리는 시간이 30초가 되게 된다.

상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

입력

---

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 T_k가 주어진다. (1 ≤ T_k ≤ 10⁹)

출력

---

첫째 줄에 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력한다.

 

문제 풀이

---

이분 탐색 문제.

 

M이 1,000,000,000까지이고 T_k가 10⁹까지이므로 정답의 범위가 매우 크다. 따라서 이분 탐색 문제를 떠올려야 한다. 이분탐색의 범위의 중간인 mid를 심사를 마치는데 걸리는 시간이라 생각하고, 해당 시간이 주어졌을 때 몇 명 심사를 마칠 수 있는지 확인해주면 된다.

만약 mid가 M보다 작다면 주어진 시간이 부족하다는 뜻이므로 mid의 값을 키울 수 있도록 left=mid+1로 값을 변경한다. 그렇지 않다면 주어진 시간이 M명 심사하는데 딱 맞거나 오히려 시간이 남는다는 뜻이다. 최솟값을 구할 수 있도록 right=mid-1로 값을 변경해준다.

 

정답은 최대 10¹⁸까지 나올 수 있으므로, 탐색 범위인 left, right, 정답인 answer 등은 모두 long long으로 정해야 한다. 또한 정답을 mid라고 가정하고, 심사를 끝낼 수 있는 사람의 수를 찾을 때 오버플로우가 발생할 수 있으므로 M명 이상인 경우는 break를 걸어주어야 한다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;
int N, M;
long long* arr;
long long answer = 1000000000000000001;

void binarySearch(long long left, long long right)
{
	while (left <= right)
	{
		long long mid = (left + right) / 2;
		long long finished = 0;
		for (int i = 0; i < N; i++)
		{
			finished += mid / arr[i];
			if (finished > M)
			{
				break;
			}
		}
		if (finished < M)
		{
			left = mid + 1;
		}
		else
		{
			right = mid - 1;
			answer = min(answer, mid);
		}
	}
	
}

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

	cin >> N >> M;
	arr = new long long[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	binarySearch(1, 1000000000000000001);
	cout << answer << "\n";
	return 0;
}