[Programmers] 입국 심사

문제

문제 요약

입국 심사를 하려고 기다리는 사람 n명, 입국 심사장마다 각각 걸리는 시간이 들어 있는 times가 주어진다.

Ex) n = 6, times= [7, 10]

모든 사람이 입국 심사를 하기까지 걸리는 시간을 구하여라.

 

https://school.programmers.co.kr/tryouts/72076/challenges

---

풀이

사람이 10만명이고, 한사람당 최대 시간이 10억이어서 시간을 하나씩 늘려가면 무조건 시간초과인데

카테고리가 이진 탐색으로 뜨길래 이진탐색인 건 알겠는데 어떤 숫자에서 이진 탐색을 하라는 거지 싶었다.

정말 모르겠어서 다른 사람의 풀이를 슬쩍 보고 답을 찾았다.

 

1. 최대로 걸릴 수 있는 시간은 times에서 가장 큰 수 * n 명

2. 그 시간 동안에 이분 탐색을 하면서 적당한 수를 선택

3. 해당 시간을 times로 나눈 몫이 사람 수와 같으면 정답, 아니면 다시 이분 탐색

def solution(n, times):    
    lw = 1
    up = max(times) * n
    
    while lw < up:
        mid = (lw + up) // 2
        people = 0
        
        for t in times:
            people += mid//t
            
            if people >= n:
                break
                
        if people >= n:
            up = mid
        else:
            lw = mid + 1
    
    return lw