[python] 백준 15903 - 카드 합체 놀이

Q> n장의 카드 중 가장 작은 카드 두 개를 더해서

덮어 쓰는 형식,

m번 반복했을 때 n장의 카드 합은?

 

🧨heapq로 풀 수 있다

PriorityQueue는 시간 초과😂 

-> PriorityQueue에서 제공하는 동기화 때문에 느리다고함

 

import sys
import heapq
input=sys.stdin.readline

n,m = map(int,input().split())  #카드 개수 n, 합체 횟수 m
a = list(map(int,input().split()))
heapq.heapify(a) # 힙으로

for i in range(m):
    temp = heapq.heappop(a)  # 가장 작은 수 pop
    temp2 = heapq.heappop(a) # 그 다음 작은 수 pop

    temp_sum = temp + temp2 # 두 수 더하기
    heapq.heappush(a,temp_sum) # 두번 넣어주기
    heapq.heappush(a,temp_sum)

print(sum(a))