[알고리즘][Python] 백준(BOJ) 15903 카드 합체 놀이_파이썬

 

15903 카드 합체 놀이    www.acmicpc.net/problem/15903

15903번: 카드 합체 놀이

 

 

문제 풀기 전 공부할 것 : 자료 구조, 그리디 알고리즘, 우선순위 큐

 

 

 

 

 

 

 

풀이

<내용>

• 우선순위 큐를 이용해서 해결한다.
• 우선순위 큐를 이용해서 카드들을 넣는다.
• 우선순위 큐를 이용해서 가장 작은 2개 카드를 꺼내서 더하고 2번 넣어준다.
• 위의 과정을 m번 반복하고 총합을 출력한다.

 

 

<코드>

import heapq

n, m = map(int, input().split())
cards = list(map(int, input().split()))
heap = []
for card in cards:
    heapq.heappush(heap, card)
    
for _ in range(m):
    x = heapq.heappop(heap)
    y = heapq.heappop(heap)
    heapq.heappush(heap, x+y)
    heapq.heappush(heap, x+y)
    
print(sum(heap))