[백준] 3079번 - 입국심사 (파이썬)

https://www.acmicpc.net/problem/3079

# 입국심사

import sys
input = sys.stdin.readline
N, M = map(int, input().split())

arr = []
for _ in range(N):
    arr.append(int(input()))

annswer = 0
left, right = 0, max(arr)*M
while left <= right:
    mid = (left+right)//2
    
    # 해당 시간으로 입국심사를 할 수 있는 사람 수 구하기
    people = 0
    for time in arr:
        people += mid//time
        if people > M:
            break
            
    if people < M:
        left = mid + 1
    else:
        right = mid - 1
        answer = mid
print(answer)

 

이분탐색
1. right을 가장 심사가 오래 걸리는 곳에서 모두 검사할 때의 시간으로 초기화
2. 이분탐색
    - 해당 시간으로 입국심사를 할 수 있는 사람의 수 구하기
    - 사람의 수가 M보다 작으면 left = mid +1
    - 아니라면 right = mid-1, answer = mid
3. answer 출력

 

어디서 봤던 문제였는데 풀고 보니 전에 프로그래머스에서 풀었던 문제였다.

[프로그래머스] 고득점Kit - 이분탐색 : 1. 입국심사 (Lv3)

[프로그래머스] 고득점Kit (9) - 이분탐색 (파이썬)