📚 1715 - 카드 정렬하기

카드 정렬하기

이해

문제를 보았을 때 이해하는데 생각보다 시간이 많이 걸렸다.

반례 테스트 케이스 를 이해한다면 문제가 쉽게 풀릴 것이다.

8
30
40
50
20
10
100
60
120

10 20
30 30
40 50
60 60
90 100
120 120
190 240

• 입력된 데이터들을 우선순위 큐에 넣은 후, 첫 번째 두 번째 데이터를 꺼낸다.
• 꺼내서 다시 우선순위 큐에 넣는다.
• 이를 반복해서 구하면 된다.
• 데이터가 하나일 때는 비교하지 않으므로 0이다.

소스

import heapq  
import sys  
  
read = sys.stdin.readline  
  
n = int(read())  
  
arr = []  
  
for _ in range(n):  
    heapq.heappush(arr, int(read()))  
  
if n == 1:  
    print(0)  
else:  
    answer = 0  
    while len(arr) > 1:  
        first = heapq.heappop(arr)  
        second = heapq.heappop(arr)  
        heapq.heappush(arr, first + second)  
        answer += (first + second)  
  
    print(answer)