[python/백준] 15903번: 카드 합체 놀이

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

15903번: 카드 합체 놀이

 

⭐문제

 

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

 

 

 

 

⭐코드분석

 

우선순위 큐 사용

 

 

 

card1 과 card2을 꺼내서 (가장작은값) 두개 다  push 

순서는 상관 없음

for _ in range(m):
    card1 = heapq.heappop(cards)
    card2 = heapq.heappop(cards)

    heapq.heappush(cards, card1 + card2)
    heapq.heappush(cards, card1 + card2)

 

 

 

 

 

⭐코드

 

from sys import stdin
import heapq


n, m = map(int, stdin.readline().split())

# heap 생성
cards = []
card_list = [int(x) for x in stdin.readline().split()]

for card in card_list:
    heapq.heappush(cards, card)

for _ in range(m):
    card1 = heapq.heappop(cards)
    card2 = heapq.heappop(cards)

    heapq.heappush(cards, card1 + card2)
    heapq.heappush(cards, card1 + card2)

print(sum(cards))