백준 1715 카드 정렬하기 - 힙

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

힙 응용 문제

왜 힙을 사용해야 하느냐?

카드를 최대한 적은 수로 비교해야 하기 때문에 계속 최솟값이 유지되어야 하고

값과 값이 더해졌을때 그 수를 힙에 넣어서 다른 수들과 다시 비교해줘야 함

import sys
import heapq
N = int(input())
heap = []
result = 0
for i in range(N):
    heapq.heappush(heap,int(sys.stdin.readline()))
for i in range(N - 1):
    temp = heapq.heappop(heap) + heapq.heappop(heap)
    heapq.heappush(heap,temp)
    result += temp
print(result)

처음에는 해당하는 예제에서는 잘 되는데 틀렸다고 뜨는 것이다... 다른건 다 잘 했는데

문제는 두 값을 더했을 때의 결과가 힙의 다른 값보다 클 경우 그 값들끼리 먼저 계산해주고 다시 힙으로 집어넣어 다시 정렬을 했어야 했다.

따라서 꼭 위 코드처럼 더한 값을 다시 heappush로 넣어줘야 했다..

또 새로 안 사실: heappop을 하기 전에는 정렬이 완전한 오름차순으로 되어있지 않지만 heappop을 하면 가장 적은 값을 출력해줌

힙아.. ㄴㅓ 처음보는데 너 참 대단하고 신기한 애구나.