[BOJ]백준 3079번: 입국심사(Python)/BinarySearch

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

3079번: 입국심사

오랜만에 다시 푼 이진탐색 문제 입국심사

loop invariant에 대해 알고난 뒤에는 탐색 범위 설정에 유의하고 나니 설계도 더 명확하게 되고 잘 풀리는 느낌이다

대부분의 이진탐색에서 공통적으로 적용되는 조건인 left < right를 제외하면,

이 문제에서는 left일 때에는 모든 사람이 통과하는 것이 불가능하고 right일 때 에는 모든 사람이 통과하는 것이 가능해야 한다.

따라서 mid 값을 두어 해당 값일 때 모든 심사대에서 통과할 수 있는 사람 수를 카운트하고, 가능/불가능 여부로 다음 탐탐색 범위를 결정한다.

import sys

sys.stdin=open('python/input.txt','r')
input=sys.stdin.readline

n,m=map(int,input().split())
t=[]

for _ in range(n):
  t.append(int(input()))

left=0
right=10**19
while left+1<right:
  mid=(left+right)//2
  cnt=0

  for time in t:
    cnt+=mid//time

  if cnt>=m:
    right=mid
  else:
    left=mid
print(right)