[파이썬/python] 백준 - 15801 풍선 공장

문제

https://www.acmicpc.net/problem/15810

---

문제 설명

1. N명의 스태프와 M개의 풍선이 존재한다.
2. N명의 각 스태프가 풍선 하나를 만드는 데 걸리는 시간 $A_i$가 주어진다.
3. M개의 풍선이 다 만들어지는 최소 시간을 출력한다.

 

---

풀이

$N$명의 스태프가 M개의 풍선을 모두 만드는데 걸리는 시간을 완전탐색을 통해 검사해보자.

최악의 경우 $10^6$명의 스태프가 존재하고 각 스태프가 풍선을 만드는 데  $10^6$ 분이 걸린다.

그렇다면 $1$부터  $10^6$초까지 모두 탐색하며 모든 풍선이 만들어 질 수 있는지 확인해야 할 것이다.

따라서 최대 시간을 T라고 했을 때 시간복잡도는 $O(N*T) = O(10^6 * 10*6) = O(10^12)$이다.

문제에서 요구하는 시간인 1초를 초과하게 되므로 부합하지 않으므로 이분탐색을 통해 문제를 풀이했다.

 

1. MAX값을 $N*T = 10^12$로 설정한다.
2. 이분탐색을 통해 현재의 시간 T에 모든 풍선을 만들 수 있는지 검사한다.
   1. 현재 T를 각 스태프가 풍선 하나를 만들 수 있는 시간을 나누어 풍선의 개수를 더한다.
   2. 총 만들 수 있는 풍선의 개수가 M보다 적다면 s = mid, 만들 수 있다면 e = mid로 변경하여 범위를 줄인다.

---

코드

import sys
input = sys.stdin.readline
MAX = int(1e12)
N,M = map(int,input().split())
times = list(map(int,input().split()))

s = 0
e = MAX
while s+1 < e:
    mid = (s+e) // 2
    cnt = 0
    for time in times:
        cnt += (mid // time)
    if cnt < M:
        s = mid
    else:
        e = mid
print(e)

---

시간복잡도

• 이분탐색의 시간복잡도는 $O(log_N)$
• 내부에서 모든 시간을 탐색하므로 총 시간복잡도는 $O(log_N * T)$
• 최악의 경우 $N = 10^6, T = 10^6$ 이므로 약 $O(20*10^6)  =O(10^7)$의 시간복잡도가 소요된다.