BOJ 15810 풍선 공장

LONGNEW·2020년 12월 31일
0

BOJ

목록 보기
16/333
post-thumbnail

https://www.acmicpc.net/problem/15810
시간 1초, 메로리 256MB
input :

  • 스태프의 수 N, 풍선의 개수 M (1 <= N <= 1,000,000)(0 <= M <= 1,000,000)
  • N명의 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai(1 <= Ai <= 1,000,000)

output:

  • M개의 풍선이 다 만들어지는 최소 시간

풍선을 만드는 시간, 스태프들에게 집중 하지 말고.
시간에 집중하자.
시간을 이분 탐색하며 가장 최댓값을 찾아내자.

N, M= map(int, sys.stdin.readline().split())
time = list(map(int, sys.stdin.readline().split()))

low = 1
high = 1000000000000

while low + 1 < high:
    mid = (high + low) // 2
    cnt = 0
    for spend in time:
        cnt += (mid // spend)
    if cnt >= M:
        high = mid
    else:
        low = mid
print(high)

0개의 댓글