백준 - 15810번 - 풍선 공장[파이썬(python)]

문제 출처 : https://www.acmicpc.net/problem/15810

15810번: 풍선 공장

 

문제

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

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

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

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

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

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

 

입력

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

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

 

출력

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

 

구현 코드

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

start = 1
end = m* max(arr)

while start <= end:
    mid = int((start + end) / 2)
    balloon = 0
    for i in arr:
        balloon += int(mid/i)

    if balloon < m:
        start = mid + 1
    else:
        end = mid - 1
        result = mid

print(result)

 

문제 해설

이 문제는 이분 탐색으로 풀 수 있는 문제이다.

최소 걸리는 시간 1분, 최대로 걸리는 시간은 풍선하나를 부는데 가장 오랜시간이 걸리는 스태프가 m개의 풍선을 불때 걸리는 시간으로 놓고 이분 탐색을 진행하여 문제를 풀 수 있다.

 

예를 들어 아래와 같은 입력이 있다고 할때, 

n = 3, m = 8

arr = [5, 7, 3]

 

step1 start = 1, end = 7 x 8 = 56, mid = int((start+end)/2) = 28

        이때 mid인 28분 동안 불 수 있는 풍선의 갯수는

        첫번째 스태프가 5개,

        두번째 스태프가 4개,

        세번째 스태프가 9개

        총 (5 + 4 + 9) = 18개 이다. 필요한 풍선의 갯수 보다 많이 때문에 시간을 줄여야 하므로 end를 감소시킨다.

        이때 end = mid - 1 = 27이 된다.

 

 

step2 start = 1, end = 27, mid = int((start+end)/2) = 14

        이때 mid인 14분 동안 불 수 있는 풍선의 갯수는

        첫번째 스태프가 2개,

        두번째 스태프가 2개,

        세번째 스태프가 4개

        총 (2 + 2 + 4) = 8개 이다. 불어야 하는 풍선의 갯수가 8개 이므로 답은 14분이 된다.