[백준] 1715 카드 정렬하기

📌문제 링크

https://www.acmicpc.net/problem/1715

💡 문제 풀이

처음에는 작은 수부터 계속 더해가면 된다고 생각했는데, 누적합이 아니라 최소합을 구하는거니까 더하는 횟수를 줄여야한다...
그래서 작은 수부터 두 개씩 짝지어서 더하고 더한 값끼리 또 더해야된다

여기까지 생각하고 나서 막혔다...
배열을 정렬하고 두 개씩 더해줄까 싶었는데 (i번째와 i+1번째 수를 더해주는 방식으로) 그 이후에 어떻게 계속 더해나가야할지가 막막했다

아이디어가 안 떠올라서 구글링을 했는데 알고보니 우선순위 큐를 사용하는 문제였다!

import heapq

heapq는 데이터를 추가, 삭제할 때마다 최소 힙을 만들어주는 모듈이라고 한다.
여기서 계속 최솟값 2개씩 꺼내 더해주고, 다시 힙큐에 넣어줘서 더해가면 된다!

참고 블로그

설명 참고
[백준/1715번/파이썬(Python)] 카드 정렬하기 / 우선순위 큐
코드 참고
[백준/파이썬] 1715 카드 정렬하기

📋코드

# 1715 카드 정렬하기
# 구글링했습니다..
# 최솟값, 최대값을 계속해서 호출할 때 우선순위 큐 (heap Queue) 사용
# heapq는 데이터 추가, 삭제시마다 자동으로 최소 힙을 만들어준다
import heapq
n = int(input())
card = []

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

result = 0
heapq.heapify(card)
# n = 1일 경우에는 비교가 필요없음
while len(card) > 1:
    # 최솟값 두 개를 꺼내 더함
    a = heapq.heappop(card)
    b = heapq.heappop(card)
    # 더한 값을 힙큐에 넣음 (새로 정렬한 카드 더미 추가)
    heapq.heappush(card, a+b)
    # 비교 횟수를 누적시킴
    result += a+b

print(result)