99클럽 코테 스터디 22일차 TIL + 이분탐색 : 입국심사

문제

링크텍스트

풀이

def solution(n, times):
    n_o = len(times)
    def f_n_i(t_i):
        n_i = 0
        for i in range(n_o):
            n_i += t_i // times[i]
        return n_i
    ts = [min(times)*n//n_o,max(times)*n//n_o+1]
    m0 = 3
    if ts[1] - ts[0] < m0:
        for i in range(10):
            if f_n_i(ts[0]+i) >= n:
                return ts[0]+i
    m = min(ts[1]-ts[0],m0)
    while ts[0] <= ts[1]:
        mu = sum(ts)//2
        ni = 0
        for ti in times:
            ni += mu//ti
            if ni >= n:
                break
        if ni >= n:
            ts[1] = mu - 1
        else:
            ts[0] = mu + 1
        if ts[1] - ts[0] < m:
            for i in range(m):
                if f_n_i(ts[0]+i) >= n:
                    return ts[0]+i
    return -1

• n_o 심사관의 수입니다.
• 만약 n_o 모두 가장 빠른 심사관으로 변경되었다면, 걸리는 시간은 min(times)*n/n_o 이고,
• 만약 n_o 모두 가장 느린 심사관으로 변경되었다면, 걸리는 시간은 max(times)*n/n_o 입니다.
• 함수 f_n_i 는 t_i라는 시간동안 과연 몇 명을 입국심사 하였는지를 구합니다.
• list ts는 입국심사에 걸리는 시간의 범위입니다. 만약 범위가 충분히 좁다면 (여기서는 3) 최소시간에서 1씩 증가시켜 함수 f_n_i를 통해 총 입국심사한 인원을 구하고 n 명을 심사하는데 걸린 시간을 구하여 반환합니다.
• 1씩 증가시켜 구하기에는 범위가 너무 넓다면, 범위의 평균값을 구하여 그 시간동안 심사한 수를 구합니다. 만약 n 보다 같거나 크다면 ts의 상한을 평균보다 1 작게 하고, 아니면 하한을 평균보다 1 크게 합니다.
• 가시 범위가 충분히 좁으면 하한에서 1씩 증가하며 n 보다 같거나 커지게 되는 시간을 구하고, 아니면 다시 구간의 평균을 구합니다. 그리고 이를 반복합니다.

결과