[BOJ 3079] 입국심사

문제 링크 : https://www.acmicpc.net/problem/3079

문제

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

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

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

예를 들어, 두 심사대가 있고, 심사를 하는데 걸리는 시간이 각각 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⁹)

출력

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

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

$M$명의 사람들이 $N$개의 입국심사대에서 심사를 마치는 데 걸리는 최소 시간을 구하는 문제다. 각 심사대마다 심사 시간이 다르며, 특정 심사대가 비었을 때 바로 이동할 수도 있고 더 빠른 심사대의 차례를 기다릴 수도 있다.

이 문제는 구하고자 하는 시간의 범위가 매우 크지만($1$부터 $10^{18}$까지), 주어진 시간 동안 처리할 수 있는 인원수가 시간에 대해 단조 증가한다는 성질을 가지고 있다. 따라서 정답이 될 수 있는 시간의 범위를 좁혀나가는 이진 탐색 알고리즘을 사용하여 효율적으로 해결할 수 있다.

핵심 로직은 다음과 같다:

1. 심사를 마치는 데 걸리는 시간의 최솟값을 left, 최댓값을 right로 설정한다.
   • left는 $1$초, right는 가장 오래 걸리는 경우($M$명이 가장 느린 심사대에서 모두 받는 경우 등)를 고려하여 충분히 큰 값인 $10^{18}$초로 설정한다.
2. 중간값인 mid 시간 동안 모든 심사대에서 처리할 수 있는 최대 인원수($total$)를 계산한다.
   • $i$번 심사대에서 mid 시간 동안 처리할 수 있는 인원은 $\lfloor mid / T_i \rfloor$명이다.
   • 모든 심사대에 대해 이를 합산한다.

\[total = \sum_{i=1}^{N} \lfloor mid / T_i \rfloor\]

1. 만약 $total \geq M$이라면, 해당 시간 내에 $M$명 이상의 심사가 가능하다는 뜻이므로 시간을 더 줄여본다 (right = mid).
2. 반대로 $total < M$이라면, $M$명을 모두 심사하기에 시간이 부족하다는 뜻이므로 시간을 늘린다 (left = mid + 1).

주의할 점은 인원수 $M$이 최대 $1\,000\,000\,000$명이고 시간도 매우 커질 수 있으므로, 연산 과정에서 오버플로우를 방지하기 위해 long long 자료형을 사용해야 한다. 또한 $total$을 계산하는 과정에서 이미 $M$을 넘어서면 반복문을 조기에 종료하여 효율성을 높일 수 있다.

이 방식의 시간 복잡도는 $O(N \log (\text{max_time}))$이며, $N = 100\,000$이고 $\log(10^{18}) \approx 60$이므로 제한 시간 $1$초 내에 충분히 해결 가능하다.

소스코드

Github Link : Source Code

참고 알고리즘 : 이진 탐색