[BOJ 3079] 입국심사 (Python3)

www.acmicpc.net/problem/3079

3079번: 입국심사

 

N, M=map(int, input().split())
T=[]
 
for _ in range(N):
    T.append(int(input()))
T.sort()
 
start=1
end=T[-1]*M
result=end
 
while start<=end:
    mid=(start+end)//2
    total=0
    for i in T:
        total+=(mid//i)
    if total>=M:
        result=min(result,mid)
        end=mid-1
    else:
        start=mid+1
 
print(result)

머리 싸매고 한 3시간 동안 고민한 문제인데.. 내가 고민한 부분은 입국 심사시간을 mid 로 해서 이분탐색 하는데-> 여기서 왼쪽으로 탐색하냐, 오른쪽으로 탐색하냐의 조건을 어떻게 정할지였다. 배열을 한번 더 돌고.. 뭐 어떻게 해야 하나??? 고민하다가 결국 안풀려서 힌트를 구글링 해본 결과... 해답은 상.당.히 간단했다.

 

입국 심사 시간 N 시간을 주면,

N시간 동안 입국심사관 1명이 처리할 수 있는 사람 수를 (N시간/입국심사관이 1명 심사하는데 걸리는 시간)으로 구하고, 그걸 입국 심사관마다 다 더해주면 되는 거였다..

처리할 수 있는 사람 수가 M명보다 많을 경우, 수를 줄이기 위해 왼쪽으로 탐색한다.

반면 M명보다 더 적을 경우 시간을 늘려야 되니깐 오른쪽으로 탐색한다.

 

여기서 포인트는 mid 값을 입국심사 시간으로 하고, 이 값에 따라 몇명을 처리할 수 있는지 계산해서 왼쪽을 탐색할 것인가 오른쪽을 탐색할 것인가 정하는 것이다. N 분 동안 몇 사람을 처리할 수 있나? 의 문제만 해결하면 쉽게 풀릴 수 있는 문제같다. 난 그 아이디어를 생각 못해서 이렇게 되었지만.