광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.
전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 (0 ≤ k ≤ 15, k는 정수) 형태이다.
광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.
첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)
둘째 줄에 충전에 필요한 시간 를 나타내는 N개의 정수가 주어진다. ( ≤ ≤ , = (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))