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

1. 문제정보

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

15903번: 카드 합체 놀이

 

2. 해결전략

우선 가장 먼저 떠오르는 해결 전략은 우선 순위 큐였다. 해당 문제를 풀기 위해서는 가장 낮은 수 2개를 뽑아서 더해주는 게 핵심이다. 우선순위큐는 O(logN)의 시간 복잡도를 가지고 가중치에 먼저 추출할 수 있기 때문에 쉽게 해결이 가능할 것이라고 생각했다.

 

 

3. 코드

from queue import PriorityQueue

n, m = map(int, input().split())

cards = list(map(int, input().split()))

que = PriorityQueue()
for i in cards:
    que.put(i)

while m > 0:
    n1 = que.get()
    n2 = que.get()
    que.put(n1+n2)
    que.put(n1+n2)
    m -= 1

print(sum(list(que.queue)))