15810번: 풍선 공장
1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에
www.acmicpc.net
문제
전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.
풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.
대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!
각 스태프가 풍선 하나를 만드는 시간(분) $A_i$를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?
풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.
모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.
입력
스태프의 수 N과 풍선의 개수 M이 입력된다. (1 ≤ N, M ≤ 1 000 000)
다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 $A_i$가 순서대로 주어진다. $A_i$는 1 000 000 이하의 자연수이다.
출력
M개의 풍선이 다 만들어지는 최소 시간을 출력한다.
코드
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
times = list(map(int, input().split()))
s, e = 0, max(times)*m
ans = 0
while s <= e:
mid = (s+e)//2
total = 0
for t in times:
total += mid//t
if total >= m:
ans = mid
e = mid - 1
else:
s = mid + 1
print(ans)
n, m의 범위가 매우 크므로 $O(logN)$의 시간 복잡도로 문제를 해결할 수 있는 매개 변수 탐색을 써야 한다.
'문제풀이 > 이분탐색' 카테고리의 다른 글
[Python/파이썬] 백준 2121번 넷이 놀기 (1) | 2023.11.15 |
---|---|
[Python/파이썬] 백준 15732번 도토리 숨기기 (1) | 2023.11.08 |
[Python/파이썬] 백준 1561번 놀이 공원 (1) | 2023.11.01 |
[Python/파이썬] 백준 17179번 케이크 자르기 (0) | 2023.10.12 |
[Python/파이썬] 백준 1300번 K번째 수 (0) | 2023.08.08 |