[백준-파이썬] 1715-카드정렬하기

문제바로가기

import heapq

n = int(input())
card = []

for _ in range(n):
    card.append(int(input()))

heapq.heapify(card)
sum_num = 0

while(len(card)>1):
    num = heapq.heappop(card)+heapq.heappop(card)
    sum_num += num
    heapq.heappush(card, num)
print(sum_num)

최종합이 적어지려면 작은수 두개씩을 묶어 더해나가면 된다. 이런 생각으로 처음에는 간단하게 배열을 정렬하고 작은수를 pop하면 두개를 더한 값이 다른 수보다 클테니까 이걸 push해서 반복해나가면 되겠다는 아주 단순한 생각이었는데 항상 두 수를 더한 값이 큰 건 아니란 걸 간과한 것이다. 그래서 결론은 우선순위가 필요하다. 결국 우선순위 큐로 다시 코드를 짰다.