[Python] 그리디- 1715. 카드 정렬하기(골4)

백준 문풀

브로코딩 2023. 8. 2. 19:26

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

>>문제 포인트(자료구조)

: 작은 값부터 출력이 가능하도록 최소힙 사용

: 계산기 예제처럼 최소1+ 최소2를 더해주고 더한값을 다시 push

: result값 출력

from heapq import heappush, heappop

heap=[]

n= int(input())

for _ in range(n):

heappush(heap,int(input()))

result=0

while(heap):

if len(heap)<2:

break

a= heappop(heap)

b= heappop(heap)

result+=(a+b)

heappush(heap, (a+b))

print(result)