[실버 1] 백준 15903 - 카드 합체 놀이 (파이썬)

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

풀이

• 숫자 카드 N장이 주어짐
• M번에 걸쳐 가장 작은 두 장을 골라 합친 뒤, 그 값을 두 장 모두에 덮어 씌움
• 최종 카드들의 합을 구하라

from queue import PriorityQueue

N, M = map(int, input().split())
A = list(map(int, input().split()))

• N: 카드 개수
• M: 합체 횟수
• A: 카드에 적힌 숫자들

pq = PriorityQueue()
for x in A :
    pq.put(x)

최소 힙을 활용하기 위해서 PrioirtyQueue에 모든 값을 넣는다. (기본적으로 오름차순 우선순위로 동작한다.)

for _ in range(M) :
    x = pq.get()
    y = pq.get()

    pq.put(x + y)
    pq.put(x + y)

가장 작은 카드 2장 x, y를 꺼낸다.

그 합 x + y를 2당 모두로 다시 삽입한다.

sum = 0
while pq.qsize() != 0 :
    sum += pq.get()

print(sum)

큐에 남은 카드 숫자들을 모두 더한다.

코드

# 백준 15903 - 카드 합체 놀이
# 분류 : 우선 순위 큐

from queue import PriorityQueue

N, M = map(int, input().split())
A = list(map(int, input().split()))

pq = PriorityQueue()
for x in A :
    pq.put(x)

for _ in range(M) :
    x = pq.get()
    y = pq.get()

    pq.put(x + y)
    pq.put(x + y)

sum = 0
while pq.qsize() != 0 :
    sum += pq.get()

print(sum)