Koala - 12기/코딩테스트 준비 스터디
[백준/python] 1715번: 카드 정렬하기
ㄱㅈㅅㅇ
2023. 10. 25. 17:12
1715번: 카드 정렬하기
정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장
www.acmicpc.net
문제 코드
from heapq import heappush, heappop
hq=[]
n=int(input())
for _ in range(n):
x=int(input())
heappush(hq, x)
#마지막에 합쳐지는수는 어차피 동일
#대신 초반부터 적게 합치고 합쳐야함.
ans=0
while(len(hq) !=1):
a = heappop(hq)
b = heappop(hq)
ans += a+b
heappush(hq, a+b)
print(ans)코드 설명
계속 합치면서 더하기 때문에 가장 적은 수끼리 더하고를 반복해야 합니다. 이때 이미 합한 값도 포함하여 가장 작은 두 개를 합쳐야하니 합한값을 다시 힙에 넣어줬습니다. hq의 길이가 1이될때까지 반복한 후 답을 출력합니다.