백준 온라인 저지, 이진 탐색/15810번: 풍선 공장(파이썬)

문제

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

 

문제 정의

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

 

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.

 

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!

 

각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

 

모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

 

 

입력

스태프의 수 N과 풍선의 개수 M이 입력된다. (1 < N ≤ 1 000 000, 0 < M ≤ 1 000 000)

 

다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.

 

 

 

출력

M개의 풍선이 다 만들어지는 최소 시간을 출력한다.

 

 

예제 입력 1

3 8
5 7 3

 

예제 출력 1

14

 

 

접근 방법

- 제작해야할 풍선의 개수가 최대인 100만개이고, 풍선 제작 시간이 최대인 100만분이 소요되는 한명의 스태프만 있을 경우 이진 탐색의 최댓값을 100만으로 잡으면 문제를 해결할 수 없다. 
- 따라서 다음과 같이 제한이 있는 경우는 100만의 제곱을 하여 시간을 늘린다.

 

 

코드

# 제작해야할 풍선의 개수가 최대인 100만개이고, 풍선 제작 시간이 최대인 100만분이 소요되는 한명의 스태프만 있을 경우 이진 탐색의 최댓값을 100만으로 잡으면 문제를 해결할 수 없다. 
# 따라서 다음과 같이 제한이 있는 경우는 100만의 제곱을 하여 시간을 늘린다.

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

making_time.sort()

start_time = making_time[0]
end_time = 1000000 ** 2
# 현재 주어진 조건(최대 시간 1,000,000 ** 2)에서 만들 수 있는 경우 이진 탐색 진행
if m > 0:
    result = end_time
    while start_time <= end_time:
        mid_time = (start_time+end_time) // 2
        count = sum([mid_time // x for x in making_time]) 
        if count >= m:
            end_time = mid_time - 1
            result = min(result, mid_time)

        elif count < m:
            start_time = mid_time + 1

elif m == 0:
    result = 0
print(result)