[BOJ 1715] 카드 정렬하기 (Python)

문제

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

1715번: 카드 정렬하기

 

풀이

초반에는 작은 수끼리 묶으면 될거라 생각해서 단순 sort하여 더하는 코드를 작성하였다. 

근데 틀렸다고 나온다. 

왜냐면 동일한 숫자 카드가 존재할 수 있기 때문이다. 

예를 들어 

3 3 3 3 

4개의 숫자카드를 순차적으로 더해나간다면 

3+3 = 6

6+3 = 9

9+3 = 12

27로 오답이 나온다. 

 

이 경우 

3+3 = 6

3+3 = 6

6+6 = 12

24가 정답이다.

결국 숫자 카드를 묶을때마다 sort를 다시 해줘야 한다는건데 

 

따라서 나는 최소 힙을 사용하여서 구현하였다.

힙 내 작은 수 두개를 뽑아 더한 다음에 

해당 값을 힙에 넣어준다. 

 

소스코드

import heapq

n = int(input())
q = []
for _ in range(n):
    heapq.heappush(q, int(input()))

result = 0
while len(q) >= 2:
    prev = heapq.heappop(q)
    cur = heapq.heappop(q)
    # print(prev, cur)
    result += prev + cur
    new = prev + cur
    heapq.heappush(q, new)

print(result)