[백준] 23843 : 콘센트

콘센트

충전에 필요한 시간은 가장 나중에 충전되는 전자기기의 출력시간이다.
이 시간이 최소화 되기 위해서는 가장 충전 시간이 긴 전자기기를 먼저 충전해놓고 , 남은 시간에 그보다 충전 시간이 짧은 전자기기를 옆 콘센트에 충전시키면 된다.

만약 1 4 8 4 1 이 있고 콘센트가 두개라면
8 먼저 충전해놓고 4 4 를 그 옆 콘센트에 연달아 충전하면 8 시간내에 충전되고 그 뒤에 둘 다 빼고 1짜리를 두 개 꽂아서 둘 중 더 늦게 충전 되는 것이 충전에 필요한 최소시간이 된다.
그리고 다시 힙에 넣을 때는 충전 시간의 누적 합을 넣어주면 따로 저장할 필요가 없다 .

import sys
import heapq
input= sys.stdin.readline
n, m = map(int, input().split())
lst = list(map(int, input().split()))
# 충전 시간이 긴 것부터 정렬
lst.sort(reverse= True)
socket = []
for i in range(len(lst)):
	# 콘센트에 자리가 있으면 일단 꽂자
	if len(socket) < m:
		heapq.heappush(socket, lst[i])
        #자리가 없으면 작은 값부터 뽑아서 다음 전자기기의 누적합을 큐에 넣어준다. 
	else:
		x = heapq.heappop(socket)
		heapq.heappush(socket, lst[i]+x)
# 가장 늦게 충전 되는 것을 출력
print(max(socket))