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

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

문제풀이

N : 입력값

hq : 우선순위 큐

 

우선순위 큐를 이용해 가장 적은 두 수를 빼가면서 정답(ans)에 더해주면 된다. 어렵지 않은 그리디 알고리즘 문제이다.

 

1. 우선순위 큐에 입력하기

 

2. hq의 크기가 1이 될때까지 hq 안의 가장 작은 두 수를 빼면서 ans에 더해준다.

- 더한 수를 다시 hq에 넣어준다.

 

코드

import sys
import heapq

if __name__ == '__main__':
    N = int(input())
    hq = []
    for _ in range(N):
        heapq.heappush(hq, int(sys.stdin.readline()))
    if N == 1:
        print(0)
        exit(0)
    ans = 0
    while len(hq) > 1:
        x = heapq.heappop(hq)
        y = heapq.heappop(hq)
        ans += (x + y)
        heapq.heappush(hq, (x + y))
    print(ans)

 

결과

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!