[python] 백준 > 이분 탐색 > 입국심사(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개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)

출력

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

 

[풀이]

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
time = [int(input().rstrip()) for _ in range(N)]

result = 0
left = 0
right = M*(min(time))

while left <= right:
    mid = (left+right)//2

    judgePeople = 0
    for t in time:
        judgePeople += mid//t
    
    if judgePeople < M:
        left = mid+1
    else:
        result = mid
        right = mid-1
print(result)

• 도대체 이걸 어떻게 이분탐색으로 접근할지 감도 안와서 구글에서 찾아보게 되었다.
• 가장 작은 시간과 사람의 명 수를 곱해서 중간값이 찾아서 접근한다는 것을 알고 어떻게 저런 생각을 하나 놀라웠다.
• 중간 값을 찾아서 그 값을 각 시간을 나눠서 합한 값이 전체 명 수보다 작으면 mid+1을 left로 두고 크면 mid-1을 right로 두되 result에 mid값을 넣어두고 마지막으로 가장 근접해지는 값을 출력해준다.

[다른 사람의 풀이]

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
arr = sorted([int(input()) for _ in range(n)])
def sol(m):
    i = 1           # 불가능한 시간의 최댓값
    M = m*arr[0]    # 가능한 시간의 최댓값
    if len(arr)== 1:
        return M
    while M-i>=2:
        j = (i+M)//2 # 중간값
        s = 0        # 심사 받은 인원의 수
        for a in arr:   
            if s < m:     # 현재 m명 미만 검사했으면 계속 검사 
                s += j//a
            else:         # 현재 m명 이상 검사 가능하면 그만
                break
        if s >= m:  # m명보다 더 검사했으면 시간의 최댓값 M을 중간값 j로 교체      
            M = j
        else:       # m명보다 더 적게 검사했으면 시간의 최솟값 i를 중간값 j로 교체
            i = j
    return M
print(sol(m))