[백준] 1715 카드 정렬하기 | Priority Queue

 

문제 보자마자 짠 코드

N = int(input())
cards = [int(input()) for _ in range(N)]
cards.sort()
s = 0

for i in range(1, N):
    s += (cards[i-1] + cards[i])
    cards[i] = (cards[i-1] + cards[i])

print(s)

 

 = 메모리 초과

뿐만 아니라 코드 내용도 잘못된 부분이 있었다..

일단 나는 그냥 정렬하고, 누적하며 더해줌

 

매번 계산 시점에서 가장 작은 두 값을 선택해서 더하는 것이 핵심인데

예를 들어 카드 1, 1, 10, 10, 10의 경우

 

 

 

따라서 Priority Queue를 사용하여, 항상 가장 작은 두 묶음을 합쳐야 한다.

(이걸 왜 미리 고려하질 못할까...?_?)

 

 

import heapq

N = int(input())
cards = [int(input()) for _ in range(N)]
heapq.heapify(cards)
s = 0

while len(cards) > 1:
    temp = heapq.heappop(cards) + heapq.heappop(cards)
    s += temp
    heapq.heappush(cards, temp)

print(s)

 

완성

앞으로 이런 문제 절대 안틀려야지