파이썬) 백준 알고리즘 | 15903번 : 카드 합체 놀이

백준 알고리즘

파이썬) 백준 알고리즘 | 15903번 : 카드 합체 놀이

코딩새내기_ 2022. 7. 1. 15:46

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

15903번: 카드 합체 놀이

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1,

www.acmicpc.net

풀이

우선순위 큐를 이용하여 풀었습니다.

카드 숫자를 heap 배열에 넣고 m번동안 가장 작은 힙 2개를 pop하고

더해서 다시 push하는 방식으로 구현하였습니다.

import heapq

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