[백준] 1715번 : 카드 정렬하기 (파이썬)

문제

나의 답안

import sys
import heapq
input=sys.stdin.readline

n=int(input())
result=[]

for _ in range(n):
    heapq.heappush(result,int(input()))#result에 원소 추가
#오름차순 정렬 됨
cnt=0
while True:
    if len(result)==1:
        break
    else:
        d=heapq.heappop(result)+heapq.heappop(result)
        #작은수부터 2개 꺼내서, 2개 더함
        cnt+=d
        heapq.heappush(result,d)#더한 값을 result에 저장-> 모두 구할 때까지 반복
print(cnt)

우선순위 큐를 위해 heapq 모듈의 사용법을 알아야 한다.

접근 방법

• 우선순위 큐, 그리디 문제이다.
• 문제 풀이를 위해 작은 수부터 2개씩 순차적으로 더해주어야 한다. heapq는 오름차순으로 저장되기 때문에 따로 정렬해줄 필요가 없다.
  (10+20)+(30+40)=100
• 2개 숫자를 더한 값을 cnt에 저장해주고, 2개 숫자의 합을 result에 저장해준다.
• 이를 result에 단일값이 저장될 때까지(len()==1)반복 해주면 된다.