[백준] 15810번: 풍선 공장 (python)

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개의 풍선이 다 만들어지는 최소 시간을 출력한다.

 

 

 

 

풀이)

일반적인 이진 탐색 문제이다. 그 중에서도 파라메트릭 서치.

생각보다 많이 틀렸는데, 그 이유가 ai의 크기도 크고, m의 크기도 커서 

적당히 크게하면 답이 나오지 않고, 너무 크게 하면 시간 초과가 나기 때문에 이 사이를 찾느라 많이 틀렸다.

 

그걸 제외하면 크게 어렵지는 않은 문제였다.

 

# 해당 시간으로 만들 수 있는 풍선의 개수
def check(x):
    total = 0
 
    for i in li:
        total += mid // i
 
    # m개 이상을 만들 수 있으면 True를 리턴한다.
    return total >= m
 
import sys
 
n, m = map(int, sys.stdin.readline().strip().split())
li = list(map(int, sys.stdin.readline().strip().split()))
 
s = 0
e = 1 << 35
ans = 1 << 35
while s <= e:
    mid = (s + e) // 2
 
    # 정답이여도 최소값이 나올 때까지 줄여간다.
    if check(mid):
        ans = mid
        e = mid - 1
 
    else:
        s = mid + 1
 
print(ans)

 

---

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

15810번: 풍선 공장