[python] 백준 1715 - 카드 정렬하기

Q> 두 묶음의 카드를 비교,

각 카드의 수가 20장, 30장이라면 비교하는데 20+30이라 할 때,

최소한 몇 번의 비교가 필요한지 출력

첫째 줄에 카드 묶음 N, 뒤의 N줄에 각 카드묶음의 크기

 

https://hyojeong94.tistory.com/120

[python] 백준 15903 - 카드 합체 놀이

위 문제와 비슷함

 

🧨위 문제와 완전 비슷한 문제

heapq를 쓰면 쉽게 풀 수 있음

(첫 골드4문제 😍)

import sys
import heapq
input=sys.stdin.readline

n=int(input().rstrip())  #n개
a=[]
for i in range(n):
    b=int(input().rstrip())  #각 카드 묶음의 수
    a.append(b)
    
heapq.heapify(a)  #heapq

result=0
for i in range(n-1): #n-1번의 연산
    temp=heapq.heappop(a)  #가장 작은 수
    temp2=heapq.heappop(a)  #그 다음 작은 수
    
    temp_sum=temp+temp2  #더해주기
    result+=temp_sum  #result에 저장
    heapq.heappush(a,temp_sum)  #더해진 숫자를 heap에 저장
    #print(a)
    
#print(sum(a))
print(result)