[백준/python] 15810번 풍선 공장

1. 문제

 

이 문제는 풍선 m개를 만드는데 걸리는 최소 시간을 구하는 문제이다.

스태프마다 만드는 속도가 다른 상황에서 짧은 시간 안에 최소 시간을 구해야 한다.

 

2. 풀이

<이분 탐색 알고리즘 적용>

1. l, r을 양 끝 숫자 0과 max(time) * m으로 초기화한다.
2. l보다 r이 크거나 같은 동안 반복문을 실행한다.
3. 두 수의 중간값 mid에 대하여 스태프마다 해당 시간에 몇 개를 만들었는지 그 합을 구한다.
4. 그 값이 m보다 크거나 같을 경우 답을 mid로 초기화하고 최솟값을 찾기 위해 r을 mid - 1로 바꾼다.
5. 아닌 경우 l을 mid + 1로 바꾸어 계속 탐색한다.

3. 코드

import sys
input = sys.stdin.readline

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

l, r = 0, max(time) * m
res = 0

while l <= r:
    mid = (l + r) // 2
    if sum([mid // i for i in time]) >= m:
        res = mid
        r = mid - 1
    else:
        l = mid + 1

print(res)

4. 느낀점

- 처음에는 어떤 알고리즘을 쓰지 않고 풀려고 노력했다. 그러나 시간초과가 떴다.

- 이분탐색 알고리즘을 제대로 사용하는 방법을 알아야겠다. r = mid-1이 아니라 r = mid로 써버려서 무한 루프에 빠졌었다.