[Python3]프로그래머스_입국심사

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43238

접근법

알고리즘 분류가 이분 탐색인 것을 몰랐다면 많이 헤맸을 것 같다.
1. 일단 먼저 최소~최대 범위를 구해야한다.

• 최소는 n이 1이더라도 포함할 수 있는 범위인 times 배열안의 가장 작은 값이고 최대는 times 배열안의 가장 큰 숫자의 n의 배수인 값이 최대이다.

2. 시작점(start)을 최소값,끝점(end)을 최대값으로 설정하여 아래 알고리즘을 반복하였다.

• mid = (start+end)//2 # 시작점과 끝점의 중간점
• sum( mid//time for time in times ) #중간점의 값을 times 배열안의 숫자들로 나눈뒤 버림을 하면 심사를 받은 사람들의 수를 구할 수 있다.
• 여기서 중간점의 값이 n보다 크거나 같다면 정답은 시작점~중간점 사이에 있고,반대의 경우 중간점~끝점 사이에 있다.
  ( n보다 크거나 같을때 시작점~중간점, 반대의 경우는 중간점+1~끝점 사이에 있다고 하는 것이 더 확실하다)

코드

def solution(n, times):
    start = min(times)
    end = max(times) * n
    while(True):
        if( end-start == 1 ):
            return start if sum(start//time for time in times) == n else end
        mid = (start+end)//2
        m = sum(mid//time for time in times)
        if( m >=n ):
            end = mid
        else:
            start = mid