📜 접근 방법
우선순위 큐를 활용
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)
💡알게 된점
'코딩테스트 > Python' 카테고리의 다른 글
[python] pccp 모의고사 1 외톨이 알파벳 (0) | 2023.03.18 |
---|---|
[python 백준 3107] IPv6 (0) | 2023.03.13 |
[python 백준 1541] 잃어버린 괄호 (0) | 2023.02.02 |
[python 백준 7662] 이중 우선순위 큐 (1) | 2023.01.29 |
[python 백준 1439] 뒤집기 (0) | 2023.01.25 |