1715번 카드 정렬하기(python)

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

1715번: 카드 정렬하기

카드 정렬하기 문제다.

내가 처음에 문제에 접근할 때는 그냥 카드 뭉치들을 정렬해주고 dp를 사용해서 작은 순서대로 카드를 더해가는 방법으로 했다. 그런데 그냥 더해가면 되는것이 아니라 그 합한 카드뭉치까지 다른 카드뭉치와 비교해서 작은순으로 비교해가야만 했다. 그래서 dp를 사용하지 않고 우선순의 queue를 사용해서 문제를 해결했다.

 

소스코드

import sys
import heapq

data = []
ans = 0
N = int(input())
for i in range(N):
    a = int(sys.stdin.readline())
    heapq.heappush(data, a)
ans = 0
for i in range(N - 1):
    a = heapq.heappop(data)
    b = heapq.heappop(data)
    ans += a + b
    heapq.heappush(data, a + b)
print(ans)