[백준] 15903번 카드 합체 놀이 파이썬 풀이

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

15903번: 카드 합체 놀이

---

1. 접근 방식

• 최소 힙을 사용하자.

카드 합체 놀이의 점수를 가장 작게 만드는 것이 놀이의 목표이다. x번 카드와 y번 카드를 고를 때, 그 두 장에 써진 수가 작을수록 그 둘의 합도 작아지기 때문에 모든 카드의 수를 더한 점수도 작아진다.

따라서 수가 가장 작은 카드를 2장 뽑기 위해 최소 힙을 사용한다.

 

• 문제 명세대로 구현하자.

문제에 카드 합체 놀이 과정이 자세히 작성되어 있으므로, 그대로 구현하자.

cards 최소 힙으로 카드 2장을 뽑고, 그 수를 더한 결과를 다시 cards에 2번 넣어주면 된다.

 

 

2. 정답 코드

from heapq import heapify, heappop, heappush

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

heapify(cards)

for _ in range(m) :
    x = heappop(cards)
    y = heappop(cards)

    heappush(cards, x + y)
    heappush(cards, x + y)

print(sum(cards))