🟩 [백준] [Python] [Silver3] 15903번_카드 합체 놀이

문제

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

15903번: 카드 합체 놀이

풀이

# 백준 15903번 문제 - 카드 합체 놀이 
import sys
import heapq
input = sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))
heapq.heapify(cards)
for i in range(m):
    value = heapq.heappop(cards) + heapq.heappop(cards)
    for _ in range(2):
        heapq.heappush(cards, value)
answer = 0 
while cards:
    answer += heapq.heappop(cards)
print(answer)

Heap 자료구조를 사용해 우선순위 큐를 만든다.

파이썬의 Heap은 최소힙이므로 따로 구현을 해줄 필요는 없다. [최대 힙을 사용하려면 -1 을 사용해 정렬]

 

힙에서 pop을 2번 하고 더한 값들을 다시 힙에 2번 넣어준다.