[백준/BOJ] - 15810번 python 풀이 - 이분탐색

 

---

Key Point

이분탐색으로 해결함

 

left를 1으로 두고 - 걸리는 시간은 자연수 이므로

right를 풍선이 나누어 떨어지지 않고(그래서+1 해줌) 가장 느리게 부는 스태프가 다 불 경우

 

mid값은 시간 이므로 해당 시간을 스태프의 풍선 부는 시간으로 나누어 주며

해당 값(mid)의 최솟값을 구하는 과정이다.

 

---

# min(arr) ~ 1000000
# mid값으로 각 스태프 풍선 부는 시간을 나눈 몫의 합이 M이랑 같으면

import sys
input = sys.stdin.readline
n,m = map(int, input().split())
arr = list(map(int, input().split()))

#1 start
left = 1
#풍선이 나누어 떨어지지 않고(그래서 +1 해줌) 가장 느리게 부는 스태프가 다 불 경우
right = (m//n+1) * max(arr)
answer = 0

while left <= right:
    mid = (left + right) // 2
    cnt = 0
    for item in arr:
        cnt += mid // item
    if cnt >= m:
        answer = mid
        right = mid - 1
    else:
        left = mid + 1
print(answer)