[백준 / Python] 23843번 콘센트

---

https://www.acmicpc.net/problem/23843

23843번: 콘센트

---

반응형

---

풀이

import sys 
import heapq 
# heapq.heappush(heap, item) : item을 heap에 추가
# heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출됨. 
# heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 

N, M = map(int, input().split())
T = list(map(int, input().split()))
T.sort(reverse = True)

answer = []

for t in T:
    if len(answer) < M:
        heapq.heappush(answer, t)
    else:
        temp = heapq.heappop(answer)
        heapq.heappush(answer, t + temp)
print(max(answer))

---

우선순위큐와 그리디 알고리즘을 이용한 풀이입니다. 

 

입력받은 data를 정렬하고 제일 적은 충전시간을 가진 전자기기부터 콘센트 개수만큼의 최소힙에 넣습니다. 

콘센트를 모두 채웠다면, 최소힙에서 하나씩 전자기기를 가져와 다음 전자기기의 충전시간을 더해 최소힙에 넣습니다. 

 

최소힙 중 가장 큰 값이 모든 전자기기가 충전되는 시간입니다.