[BOJ 15903, Python 3] 카드 합체 놀이

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

15903번: 카드 합체 놀이

 

풀이

두 카드를 선택하고 점수를 합친 값을 선택한 두 카드의 값으로 재설정한다고 합니다.

이렇게 M번 반복하고, 카드들의 합이 최소화가 되는 것을 원한다고 합니다.

최소화를 하려면 가장 작은 2개를 선택하면 된다는 것을 알 수 있습니다.

 

코드는 heapq를 사용하였는데, for문 돌릴때마다 sort를 사용해도 상관 없습니다.

코드

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