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

https://programmers.co.kr/learn/courses/30/lessons/43238

처음 문제를 봤을때는 왜 이분탐색이지? 고민을 좀 하였다.
일단, 입력데이터가 1,000,000,000인 수가 있으므로 완전탐색을 진행하면 바로 시간초과가 날 것이라고 판단하였다.

심지어 1,000,000,000 * 1,000,000,000이라는 수가 저장이 될까도 고민하였지만 파이썬의 정수 범위는 무려 -9223372036854775808 ~ 9223372036854775807 라고 찾았다.

2가지 정도의 생각이 들어갔는데 다음과 같다.

• 이분탐색 : 걸리는 시간의 후보군에서 가장 작은 정답을 골라야 한다.(이를 이분탐색법으로), 또한 후보군이 정답이 될 수 있는지 판단하는 함수가 필요하였다.
• 후보군이 정답이 될 수 있는지 판단부분이 생각이 잘 안났는데 해당 시간 만큼 각각의 심사위원이 사람을 얼마나 많이 받을 수 있는지 고려하여 더하여 그 누적값이 사람의 수를 포함하면 그 시간은 정답이 될 수 있다.
  (가령, 예제에서 30이란 시간에 6명을 전부 받을 수 있는가 고려를 해 본다면 7-심사위원은 최대 4명을 받을 수 있고 10-심사위원은 최대 3명을 받을 수 있어서 7명까지 커버가 가능하다.)

from functools import reduce


def check(mid, times, n):
    if n <= reduce(lambda acc, cur: acc + int(mid / cur), times, 0):
        return True
    return False


def solution(n, times):
    answer = 0
    max_num = max(times)

    left = 0
    right = max_num * n

    while left < right:
        mid = int((left + right) / 2)
        if check(mid, times, n):
            answer = mid
            right = mid
        else:
            left = mid + 1

    return answer

Reference

https://technote.kr/183