[python 백준 1715] 카드 정렬하기

📜 접근 방법

우선순위 큐를 활용

1. 힙에다 주어진 숫자들를 넣는다.

2. 만약 숫자가 1개만 주어지면 합칠것이 없으니 0 출력 후 종료

3. 힙에 숫자가 2개 이상일 경우 반복

    1. 가장 작은 수 2개를 뽑은 후 그 숫자를 더한다.
    2. 그 후 그 두 숫자를 더한 후 힙에 넣어준다.

4. 결과값 출력

 

 

❌ 실패 이유

 

카드를 섞은 후 그 값도 포함시켜서 가장 작은 수를 찾아야하는데 그대로 더해서 최소값이 나오지 않았다.

 

 

✅ 정답 코드

import sys
import heapq

n = int(sys.stdin.readline())
heap = []

for i in range(n):
    heapq.heappush(heap, int(sys.stdin.readline()))


if n == 1:
    print(0)
else:
    res = 0
    while len(heap) >= 2:
        sm1 = heapq.heappop(heap)
        sm2 = heapq.heappop(heap)
        res += sm1 + sm2
        heapq.heappush(heap, sm1 + sm2)
    print(res)

💡알게 된점