[BOJ] 23843 콘센트 (python)

문제

광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.

전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 $2^k$(0 ≤ k ≤ 15, k는 정수) 형태이다.

광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.

입력

첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)

둘째 줄에 충전에 필요한 시간 $t_i$를 나타내는 N개의 정수가 주어진다. ($2^0$ ≤ $t^i$ ≤ $2^{15}$, $t^i$ = $2^k$ (0 ≤ k ≤ 15, k는 정수))

출력

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

풀이

우선 순위를 둔 heapq를 이용해서 풀면 된다.
콘센트에 시간이 오래걸리는 순서대로 충전을 시작하고, 충전이 다되어 빈 콘센트가 생길 때 마다 남은 전자기기 중에서 충전에 가장 시간이 오래 걸리는 것을 충전시키며 시간을 계산해나가면 된다.
시간 계산은 이 때까지 걸린 시간 + 지금 콘센트에 꽂을 전자기기의 걸리는 충전 시간을 이용해서 마지막에 가장 큰 값을 확인하면 된다.

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))