[백준] 1715번 파이썬 _ 카드 정렬하기

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

1715번 맞은 사람 - 1 페이지

문제유형 : 그리디, 우선순위큐 

 

문제풀이 : 

• 앞에서 더한카드의 숫자가 계속해서 누적되기 때문에 가장 작은 카드들부터 2개씩 뽑아서 더해줘야한다.
  • 가장작은 카드를 반복적으로 뽑아내기때문에 힙큐모듈을 사용해서 우선순위큐를 사용한다.
• 주어진 예제케이스가 카드 3개인 테스트케이스여서 처음 생각에 실수가 있었다. 앞에서 더한 카드의 결과가 꼭 다음카드를 합칠때 사용되어야하는게 아니다. 20,20,20,10,10이 있을때 10,10,을 더하면 남은카드가 20,20,20,20이 되기때문에 20,20 을 더한후 40,20,20일때 아까 더한것은 두고 20,20을 또 더하고 남은 40,40을 더하는것이다. 

 

 

정답코드 :

import sys
import heapq
input = sys.stdin.readline

number = []
n = int(input())
for _ in range(n):
    number.append(int(input()))
number.sort()

q = []
for num in number:
    q.append(num)

sum = 0
result = 0
while len(q)>1:
    print(q)
    sum = heapq.heappop(q) + heapq.heappop(q)
    result += sum
    q.append(sum)

print(result)