백준 문제풀이 - 15810 번

링크 -> https://www.acmicpc.net/problem/15810

1. 요약 및 풀이방법

M개의 풍선을 불어야 하는데 N명의 스태프가 풍선부는 속도가 다를 때,
최소 몇분이 걸리는지 구하는 문제입니다.

이 문제는 고용주 입장에서 생각해보면 편합니다.
스태프들에게 허락 할 시간의 범위를 정하고, 이를 이분탐색 하여 구하면 간단합니다.
아래 코드의 경우,
start(허락 할 최소시간) = 전부다 가장 빨리 부는 스태프라고 가정
end(허락 할 최대시간) = 전부다 가장 느리게 부는 스태프라고 가정

이와같이 범위를 정한 후, 해당 시간에 각 스태프가 불 수 있는 풍선의 갯수를 모두 더해서
적게 불었으면 시간을 더주고, 많이 불었으면 시간을 덜 주는 방향으로 update합니다.

2. Code

def main():
    N, M = map(int, input().split())
    times = list(map(int, input().split()))

    start = (M // N) * min(times)
    end = (M // N + 1) * max(times)
    ans = 0
    while start <= end:
        mid = (start + end) // 2

        count = 0
        for time in times:
            count += mid // time

        if count < M:
            start = mid + 1
        else:
            ans = mid
            end = mid - 1

    print(ans)

if __name__ == "__main__":
    main()

3. 학습 내용

이번에는 특히 start, end를 잘 초기화하는것에 초점을 두었습니다.
이분탐색 방법 자체가 빠르긴 하지만, 그 범위조차 작게 만들어둔다면 더 효율적으로 구할 수 있습니다.
위의 풀이방법에 적어 둔 대로 초기화를 하니, python으로 푼 다른 코드들에 비해 시간이 적게 걸림을 확인했습니다.

4. 결과