[테스트케이스추가] 백준 1715번: 카드 정렬하기

1. 문제

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

1715번: 카드 정렬하기

 

 

2. 풀이

우선순위 큐

 

 

3. 구현

import sys
# sys.stdin = open('input.txt')
import heapq
lis = []
n = int(sys.stdin.readline().strip())
while n:
    n-=1
    tmp = int(sys.stdin.readline().strip())
    heapq.heappush(lis, tmp)
    
answer=0
# if len(lis)==1 -> no comparision
while len(lis)>1:
    a=heapq.heappop(lis)
    b=heapq.heappop(lis)
    answer+=(a+b)
    heapq.heappush(lis, a+b)
sys.stdout.write(str(answer))

 

 

4. 반례 + 테케

 

@bamgoesn  님

4
30
40
50
100

답: 410

 

4
30
40
50
60

답: 360

 

8
30
40
50
20
10
100
60
120

답: 1160

 

8
30
40
50
20
10
100
60
10

답: 860

 

4
120
40
100
20

답: 500