BOJ 3079번: 입국심사

www.acmicpc.net/problem/3079

3079번: 입국심사

아이디어:

시간을 이분탐색하여 시간의 최솟값을 찾는다.

 

import sys
n, m = map(int, sys.stdin.readline().split())
time = []
for _ in range(n):
    time.append(int(sys.stdin.readline()))
high = 10**18
low = 1
ans = high
while (high>=low):
    mid = (high+low)//2
    total = 0
    for t in time:
        total += mid//t
        if (total>=m): break #오버플로우
    if (total>=m):
        ans = mid ##
        high = mid - 1
    else:
        low = mid + 1
print(ans)

※ 오버플로우 나는 부분 주의

※ 처음에 그냥 mid를 출력하면 될 거라고 생각했는데.. total<m인 경우도 있으니까 total>=m인 경우에만 mid를 ans로 업데이트 해서 while 문을 모두 돈 후 ans를 출력해야 한다.