[BOJ 15810🥈2] 풍선 공장 (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개의 풍선이 다 만들어지는 최소 시간을 출력한다.

예제 입력 1 

3 8
5 7 3

예제 출력 1

14

 

⭕ CODE

n,m = map(int,input().split())

arr = list(map(int,input().split()))

# 시작은 최소 0
# 끝은 가장 적은 시간이 걸리는 사람이 다 만드는 경우로 지정
start = 0
end = min(arr) * m

# start <= end 로 지정하면 무한루프에 빠지게 되어서 start+1 < end로 지정

while start+1 < end:
    # 중간값 지정
    mid = (start+end) // 2
    # 가능한 풍선의 개수
    result = 0

    for i in range(n):
        result += mid//arr[i]

	# 풍선이 m개보다 같거나 많으면
    if result >= m:
    	# 끝지점을 중간지점으로 
        end = mid
    # 그게 아니라면
    # 시작지점을 중간지점으로
    else:
        start = mid

print(end)

✏️ Comment

처음에는 이분탐색 문제임을 인지하지 못하였다. n,m이 1000000이하임을 보고 알아차렸어야했다.

while 조건을 이분탐색을 사용하다보면 start <= end로만 사용해서 처음에는 무한루프에 빠지게 되어서 시간초과가 나왔다. while 조건을 잘 생각하자