백준 알고리즘 15903: 카드 합체 놀이(Python)

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

15903번: 카드 합체 놀이

---

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 해결할 수 있는 문제였습니다. 먼저 문제를 잘 보시면 리스트에서 가장 작은 값 2개를 빼온 후 그 둘의 합을 구합니다. 그 후 합들을 리스트에 넣어줍니다.

문제 해결을 위한 팁

이때 가장 작은 값을 두 개 빼오는 과정은 sort()를 이용하여 구할 수도 있고 우선순위 큐를 이용할 수 있습니다. 파이썬의 우선순위 큐는 최소합으로 구현이 되어있기 때문에 단순히 우선순위 큐에서 빼내기만 하면 가장 작은 값을 빼올 수 있습니다.

소스코드

import heapq
n, m = map(int, input().split())
data = list(map(int, input().split()))
q = []
for i in range(n):
  heapq.heappush(q, data[i])
 
for i in range(m):
  x = heapq.heappop(q)
  y = heapq.heappop(q)
  heapq.heappush(q, x+y)
  heapq.heappush(q, x+y)
 
print(sum(q))