백준 1715 카드 정렬하기

김민영·2023년 2월 9일
0

알고리즘

목록 보기
118/125

문제

  • 숫자 카드를 비교하고, 비교한 숫자 카드는 합친다.
  • 모든 숫자 카드에 대해 위 과정을 반복한다고 하면, 숫자 카드를 비교한 횟수의 최소값을 구한다.

과정

  • 그리디 : 남은 숫자 카드 중 가장 작은 두 카드를 비교하고 합쳐야한다.
    • 카드를 비교할 때마다 비교한 카드 수는 답에 더해지게 된다.
    • 더해지는 수가 작으려면 가장 작은 두 카드를 비교해야 한다.
  • 우선순위 큐를 사용해서 남은 카드 중 가장 작은 값을 가진 카드 두 개를 구해야 한다.
import sys
import heapq

N: int = int(input())

ans: int = 0

q = []
for i in range(N):
    inp: int = int(input())
    heapq.heappush(q, inp)

ans = 0

while len(q) >= 2:
    a = heapq.heappop(q)
    b = heapq.heappop(q)
    ans += a + b
    heapq.heappush(q, a + b)

print(ans)
profile
노션에 1차 정리합니당 - https://cream-efraasia-f3c.notion.site/4fb02c0dc82e48358e67c61b7ce8ab36?v=

0개의 댓글