[백준 1715] 카드 정렬하기

1. 문제

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

2. 접근 방법

가장 작은 크기의 두 카드 묶음을 합쳐야한다. 

--> 매 상황에서 가장 작은 크기의 두 카드 묶음 !!

 

--> 우선 순위 큐 사용

 

3. 코드

python

import sys, heapq
input = sys.stdin.readline
N = int(input())

heap = []
for i in range(N):
    heapq.heappush(heap, int(input()))

ans = 0

while len(heap) != 1:
    one = heapq.heappop(heap)
    two = heapq.heappop(heap)
    sum_val = one + two
    ans += sum_val
    heapq.heappush(heap, sum_val)

print(ans)

4. 마치며

처음에 문제 풀었는데 4100ms나와서 뭐지 ..... 왜 ... 8ㅅ8 .. 이랬는데

알고보니 입력에서 속도가 느렸던 것 .. 

흥

 

입력만 바꿔도 4초가 줄어욧