[Python] 15810번 풍선 공장

✏️ 문제

 

문제 파악

풍선의 개수는 해당 시간에서 각 시간을 나눈 몫의 합이라는 걸 알면 쉽게 풀 수 있다!

최대 시간을 end로 주는 걸 생각 못하고 end 없이 코드를 어떻게 짜야하지 .. 하고 있었던 ..

 

알고리즘

• 매개 변수 탐색
• 이분 탐색

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

start, end = 1, max(a) * m
while start <= end:
  mid = (start+end) // 2
  balloon = 0
  
  for i in range(n):
    balloon += mid // a[i]

  if balloon >= m:
    end = mid - 1
  else:
    start = mid + 1

print(start)