[BOJ] 23843 콘센트 (python)

문제

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.
전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2k(0 ≤ k ≤ 15, k는 정수) 형태이다.
광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

입력

첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)
둘째 줄에 충전에 필요한 시간 ti를 나타내는 N개의 정수가 주어진다. (20 ​≤ ti ≤ 215, ti = 2k (0 ≤ k ≤ 15, k는 정수))

출력

충전에 필요한 최소 시간을 출력한다.

풀이

시간이 오래걸리는 전자기기부터 충전하면 된다.
우선 충전에 걸리는 시간을 내림차순으로 정렬한 후 하나씩 heapq에 집어넣고 최대 콘센트 수 만큼 넣어졌을 경우 먼저 충전되는, 즉 값이 낮은 순서부터 하나씩 pop한 후 새로 충전할 기기의 소요 시간을 더해서 다시 넣어주면 된다. 이렇게 하면 새로 들어오는 기기는 이전까지 충전했던 시간 + 해당 기기를 충전하는데 걸리는 시간을 더한 시간만큼 소요해야 충전이 된다.
모든 기기에 대해 반복문 수행 후 가장 오래 걸린 시간을 출력해주면 최소 시간이 된다.

import sys
import heapq

num_device, num_concent = map(int, sys.stdin.readline().split())
time_require = sorted(list(map(int, sys.stdin.readline().split())), reverse=True)

concent = []
for t in time_require:
    if len(concent) < num_concent:
        heapq.heappush(concent, t)  # 콘센트 비었으면
    else:
        charged = heapq.heappop(concent)    # 완충
        heapq.heappush(concent, charged+t)  # 다음 충전할 것 push
print(max(concent))