[백준][Python] 1715번 카드 정렬하기 - 골드 4

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

1715번: 카드 정렬하기

문제

 

풀이

우선순위 큐를 활용하여 문제를 구해주면 됩니다. 문제의 예시를 통해 직접 구해보면 알다시피 다음과 같은 로직이 성립하게 됩니다.

 

1. 큐 안에서 가장 작은 수 2개를 꺼내서 더해준다.

2. 더한 값을 총합(변수:ans)에 더해준다.

3. 더한 값을 다시 큐에 넣어준다.

4. 1-3과정을 큐 안에 원소가 2개 이상일 때까지 반복해준다.

 

코드

# 1715번 카드 정렬하기
from heapq import heappop, heappush
import sys

queue = []
n = int(input())
for _ in range(n):
    heappush(queue, int(sys.stdin.readline()))

ans = 0

while len(queue) > 1:
    minimum_first = heappop(queue)
    minimum_second = heappop(queue)
    new_num = minimum_first + minimum_second
    ans += new_num

    heappush(queue, new_num)

print(ans)

 

출력결과