2022.02.16 [백준] (python 파이썬) 카드 정렬하기

 

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

1715번: 카드 정렬하기

 

---

풀이

이 문제를 3가지 조건으로 생각했다.

1. 카드더미가 1개만 들어왔을 경우 계산할 필요가 없으므로 바로break걸어서 0출력

2. 카드더미가 2이상일 경우 heap에서 최소값을 2개 뽑아서 더한 후, 더한 값을 다시 heap에 push하고,

   더한 값을 ans에 더함.

3 카드더미가 2개일 경우 최소값2개를 뽑아 더한 후 ans에 출력. 그리고 while 문 끝남(2개남은 것을 pop해서 heap안에 데이터가 없기 때문)

import heapq
import sys
 
input=sys.stdin.readline
 
n=int(input())
 
heap=[]
for _ in range(n):
    heapq.heappush(heap, int(input()))
 
ans=0
 
while heap:
    if n==1:
        break
    if len(heap)>2:
        a=heapq.heappop(heap)
        b=heapq.heappop(heap)
        heapq.heappush(heap,a+b)
        ans+=a+b
    elif len(heap)==2:
        a=heapq.heappop(heap)
        b=heapq.heappop(heap)
        ans+=a+b
 
print(ans)