[baekjoon] 15903. 카드 합체 놀이

✅ 문제

 

---

✅ 풀이

이 문제는 생각보다 간단하다. 최솟값만을 이용하니 힙정렬을 이용하자

💡 Point
가장 작은 수를 지닌 카드 두 개(x, y)를 더한 값을 다시 카드 리스트에 넣어줘야 함
1) 두 카드를 제거 - heappop() 2번
2) x+y 값으로 덮어씀 - heappush() 2번

 

import heapq

# 카드 합체 놀이
# n: 카드 개수, m=합체 횟수
n, m = map(int, input().split())
cards = list(map(int, input().split()))

#리스트를 힙으로 변환
heapq.heapify(cards)
for i in range(m):
    # 제일 작은 수 두개 뽑아내기
    x = heapq.heappop(cards)
    y = heapq.heappop(cards)
    
    # 더한 값을 다시 힙에 넣기(덮어쓰기)
    heapq.heappush(cards, x+y)
    heapq.heappush(cards, x+y)

print(sum(cards))