[백준] 3079 입국심사 with Python

📌 BOJ 3079 입국심사

💡 조건

1. 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다.
   (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)

2. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다.
   k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다.
   (1 ≤ Tk ≤ 109)

3. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에,
   지금 심사를 기다리고 있는 사람은 모두 상근이와 친구들이다. 한 심사대에서는 한 번에 한 사람만 심사를 할 수 있다.

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

5. 상근이와 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제.

6. 이분탐색 유형의 문제

🖥 소스 코드

from sys import stdin

n, m = map(int, stdin.readline().split())
arr = [int(stdin.readline()) for _ in range(n)]

l, r = min(arr), max(arr) * m
ans = r

while l <= r:
    total = 0
    mid = (l + r) // 2

    for i in range(n):
        total += mid // arr[i]

    if total >= m:
        r = mid -1
        ans = min(mid, ans)

    else:
        l = mid + 1

print(ans)

🔖 예제 및 실행결과

예제

7 10
3
8
3
6
9
2
4

실행결과

8

⌨️ 문제 풀이

1. 그리디 혹은 브루트포스로 문제를 풀게되면, 인원 수 M 의 최대 크기가 10억이기 때문에 반드시 시간초과로 틀리게 된다.

2. 이분탐색으로 문제를 풀어야하는데, 심사대에서 한명이 심사를 받는 최소 시간을 l,
   심사대에서 m 명이 심사를 받는 최대 시간을 r 로 정한다.
   이에 따라 l = min(arr), r = max(arr) * m 이 된다.

3. 이분탐색을 위해 while 문을 사용하는데, 조건은 l 이 r보다 작거나 같을 때만 반복이다.
   m 명이 심사를 모두 받는 시간을 mid라고 했을 때, mid = (l + r) // 2 이다.
   이 mid 값을 사용하여 최소 시간을 구한다.

4. n 개의 심사대의 정보가 있는 arr 리스트를 순회(i)하면서, mid 시간에 i 번 심사대에서 심사를 받을 수 있는 인원을 total 변수에 저장한다.

5. arr 리스트를 모두 순회했다면, total 값과 m의 값을 비교하여 모든 인원이 심사대에서 심사를 받았는지 확인한다.
   여기서 total 값이 m 보다 작다면 모든 인원이 심사를 받지 못한 것이므로, l 을 mid + 1 로 갱신한다.

6. (5) 번의 조건에서 total 값이 m 보다 크다면 모든 인원이 심사를 받을 충분한 시간인 것이다.
   mid 값과 answer 값을 비교하여 더 작은 값을 answer 값으로 갱신한 뒤,
   r 을 mid - 1로 갱신하여 m 명이 모두 심사를 받는 더 작은 최소 시간이 있는지 검사한다.