알고리즘 스터디 - 백준 3079번 : 입국심사

문제 해석

입국심사 시간이 최소가 되는 프로그램을 작성해야함

1. M명이 여행을 감
2. 입국심사대 개수는 N
3. 각 입국 심사대에서 심사가 걸리는 기간은 Tk임

어떤 알고리즘을 써야할까?

여기서 2개의 입국심사대에 6명이 있고 입국심사대 2개의 심사기간은 각각 7초 10초이다. 걸리는 시간을 기준으로 배열을 만들어 보자

• 7초 배열 : [7, 14, 21, 28, 35, ...]
• 10초 배열 : [10, 20, 30, 40, 50, ...]

2개의 배열을 섞어보자

• 최종 배열 : [7, 10, 14, 20, 21, 28, 30, 35, 40, 50, ...]

이렇게 섞은 배열에서 6번째 위치를 찾으면 답이 나온다. 근데 우리는 N이 커질 수록 각 배열을 어디까지 생성해야하는 것일까? 라는 어려움이 생기게 된다. 이 경우 잘 못하면 메모리가 초과할 수 있다. 따라서, 다른 방법을 생각해보자.

사람이 6명이면 명칭을 0~5라는 숫자로 해보자

7초 배열 : [0, 2, 4, 5]
10초 배열 : [1, 3]

통과하는 승객 수 = 주어진 시간 // 심사대 시간
이진 탐색 알고리즘을 사용해서 주어진 시간을 1~효율이 안좋은 심사대 * 승객수 사이에서 값을 움직이면 된다.

알고리즘 코드

이진 탐색 과정에서 M이상일 경우 mid_value - 1로 지정을 하면 찾지 못한다. 생각해보니 각각의 상황에 맞게 최적화한 승객 수를 줄여버리니 매칭이 되는 것을 찾을 수가 없기 때문이다.

# 심사대와 승객 입력 받음
N, M = map(int, input().split())

# 심사대 걸리는 시간을 순서대로 집어넣음
Tk = []
for _ in range(N):
    time = int(input())
    Tk.append(time)

# 효율이 제일 안좋은 최댓값
max_value = max(Tk) * M
low_value = min(Tk)

# 이진 탐색 진행
while low_value < max_value:
    # 효율의 중간 값을 찾고
    mid_value = (low_value + max_value) // 2

    # 통과하는 승객 수
    require_value = 0
    
    # 통과하는 승객 수 = 주어진 시간 // 심사대 시간
    for i in range(N):
        require_value += mid_value // Tk[i]
    
    if require_value < M:
        low_value = mid_value + 1
    else:
        max_value = mid_value

print(max_value)