입국심사

접근방식

일단 https://wwlee94.github.io/category/algorithm/binary-search/immigration/ 참고하여 풀었다.
너무 어렵게 생각했었다.
아 짜증나고 존심 상한다. ㅋㅋㅋㅋㅋ

이분 탐색을 활용해야한다. 왜냐하면 문제에서 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하 이기 때문에 단순한 for 문으로 탐색하다간 시간 초과각이다.

이분 탐색의 응용인 매개 변수 탐색을 활용해야 하는데, 매개 변수 탐색의 결정 함수를 문제에 알맞게 정의하는게 관건이다.

n명을 모두 심사할 수 있는 전제 하에 가장 최소시간을 구해야한다. 다시 말해, 최대 hi, 최소 lo 범위를 설정한 뒤 n명을 모두 심사할 수 있는 시간을 의미하는 mid값들 중에서 최소값을 구해야한다.

코드

# 결정 함수 fn
def fn(param, times, n): # param이 곧 mid 값
    count = 0
    for time in times:
        count += param // time
        if count >= n:
            break
    return count


def solution(n, times):
    times.sort()

    lo = 0 # 최소
    hi = times[-1] * n + 1 # 최대
    while lo + 1 < hi:
        # mid는 입국 심사 시간을 의미한다.
        mid = (lo + hi) // 2
        temp = fn(mid, times, n) 
        
        if temp >= n: 
            # 입국 심사 시간(=mid) 동안 n명을 모두 검사할 수 있다면 
            # -> mid중 최소값을 구해야 하므로 hi를 mid로 설정하여 하위 범위 탐색
            hi = mid
        else:
            # 입국 심사 시간(=mid) 동안 n명을 모두 검사할 수 없다면 
            # -> n명을 모두 심사할 수 있는 시간을 찾기 위해 lo를 mid로 설정하여 상위 범위 탐색
            lo = mid
    # 최소 lo을 0으로 초기화 했기 때문에 +1 해준다.
    return lo + 1


print(solution(6, [7, 10])) #28
print(solution(6, [6, 10]))  #24
print(solution(6, [8, 10])) #30
print(solution(6, [4, 10])) #20
print(solution(11, [3, 4, 10])) #18
print(solution(5, [1, 1, 10])) #3
print(solution(3, [1, 1, 1])) #1
print(solution(3, [1, 2, 3])) #2