[python] 백준 3079번 입국심사

백준 3079번 입국심사

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

문제

풀이

import sys
input = sys.stdin.readline

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

nlist.sort()

start = 1
end = nlist[-1] * m

while start <= end: 
    mid = (start + end) // 2

    count = 0
    for i in nlist:
        if mid >= i:
            count += mid // i
    
    if count < m: 
        start = mid + 1
    
    else:
        answer = mid 
        end = mid - 1

print(answer)

📌 주의

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000)
숫자보고 이분탐색으로 풀어야겠다라고 생각...
근데 항상 다른 방법이 있을 것이라고 착각하게 되는 문제 중 하나.

• start 는 항상 0 이나 1 에 두기.
• end 는 최악의 경우에다 두기.
• print(mid)를 할 경우, start, mid, end는 이미 값이 변질되어버리기 때문에 answer 를 꼭 사용하기.