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

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

3079번: 입국심사

• 이 문제는 처음 문제를 읽으면서 생각했을 때는 그리디 처럼 풀려고 했다.
• 하지만 최소값을 구하는 과정에 있어서 이분탐색을 생각하게 됐고,
• 이분탐색으로 풀이를 했다.
• 이 문제는 관점이 중요했다. 사람을 먼저보는게 아닌 심사대에 몇 명을 넣을 것인지를 생각하면서 풀이하였다.

#이분탐색
import sys
input = sys.stdin.readline

n,m = map(int,input().split())
data = [int(input()) for _ in range(n)]

start = 1
end = m*max(data)
# m명을 심사할 수 있는지 없는지를 파악하는 문제이다.
# 1561과는 이점에서 다르다.
while start<=end:
    mid = (start+end)//2
    print(mid)
    cnt =  0 
    for i in range(n):
        cnt += mid//data[i]
    if cnt>=m: 
        time = mid
        end = mid-1
    else:
        start = mid+1
print(time)