[백준/Python] 1279번 : 풍선공장

 

https://www.acmicpc.net/problem/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

힌트

1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 1번 스태프가 1개를, 12분에 3번 스태프가 1개를, 14분에 2번 스태프가 마지막 1개를 만들면 총 14분으로 최소 시간이 걸린다. 

접근

뭔가 이 문제를 잘 이해하고나서 이분탐색이라는것에 접근하기가 쉬워졌다고 생각한다.

주의할점은, "이분탐색" 이라는것은 최대 혹은 최소에서 서서히 내려오거나 올라가는게 아니라, 정말 왔다갔다 하면서 찾는것이다.

즉, 당장은 정답(근사치)에서 멀어지는 방법이 결국 멀리서봤을때는 정답에 가까운 방법임.

우선 풍선이 다 만들어지는 "최소" 시간을 출력하는것이기때문에, 정말 적어도 주어진 풍선을 만드는 시간의 최솟값 x M 보다는 시간이 같거나 적게 걸릴것이다.

극단적으로 예를 들어보면, N이 3, M이 10 이고 3명의 스태프들이 풍선 하나를 만드는데 걸리는 시간이 다음처럼 주어진다고 가정해보자.
100, 100, 3 

그렇다면 아무런 과정이 없어도 min(시간들) x M, 즉 30분보다는 같거나 적게걸린다는것을 알수있음.

때문에, min을 1로, high를  min(time)*M 로 설정하면서 이분탐색을 진행하였다.

그리고 while문에서 한바퀴 돌때마다, 현재 mid 값으로 풍선을 만드는데 걸리는 시간들을 다 나눠보면서, 실제 만들수있는 풍선의 값과 문제에서 주어진 M값을 비교하면서 low, high값을 재설정해주었다.

 

코드

import sys

input = sys.stdin.readline
N, M = map(int, input().strip().split())

time = list(map(int, input().strip().split()))

low, high = 1, min(time)*M

while low <= high:
    mid = (low + high) // 2
    ballons = 0
    for i in range(N):
        ballons  = ballons + (mid // time[i])

    if ballons < M:
        low = mid + 1
    elif ballons >= M:
        high = mid - 1
print(low)