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

15903번: 카드 합체 놀이

 

코드

import heapq

n,m = map(int,input().split())
n_list = list(map(int,input().split()))
heapq.heapify(n_list)
for _ in range(m):
	a = heapq.heappop(n_list)
	b = heapq.heappop(n_list)
	heapq.heappush(n_list,a+b)
	heapq.heappush(n_list,a+b)
print(sum(n_list))

 

설명

heapq의 heapify를 사용하면 입력받은 리스트를 힙으로 변환할 수 있다.

파이썬에서 제공하는 heapq는 최소힙이기 때문에 heappop을 하면 힙에서 가장 작은 수를 반환해준다.

따라서 heappop을 두 번 해서 각각 a와 b에 저장하고 둘을 더한 값을 두 번 heappush로 힙에 넣어준다.

위 과정을 m번 반복한 뒤 sum을 이용해서 총합을 구한다.