1715

날짜 : 2022. 09. 23

사용 언어 : python

 

문제

 

코드

틀린코드(알고리즘 자체가 틀림)

import sys

n = int(sys.stdin.readline())
card = list()
card.append(0)
if n == 0:
    print(card[0])
else:
    nums = list()
    for i in range(n):
        t = int(sys.stdin.readline())
        nums.append(t)

    nums.sort()
    for i in range(len(nums)):
        result = card[i]+nums[i]
        card.append(result)
    total = 0
    for i in range(2, len(card)):
        total += card[i]
    print(total)

 

정답코드

import sys
from queue import PriorityQueue

n = int(sys.stdin.readline())
if n == 1: # 비교 필요 x
    print(0)
else:
    result = 0
    deck = PriorityQueue() # 우선순위 큐 형태의 덱 목록
    for i in range(n):
        t = int(sys.stdin.readline()) # 카드 입력
        deck.put(t) # 카드 목록에 넣음
    while deck.qsize() > 1:
        a = deck.get() # 가장 작은 수의 덱 추출
        b = deck.get() # 두번째로 작은 수의 덱 추출
        s = a + b # 결합
        result += s
        deck.put(s) # 해당 덱 넣음
    print(result)

 

알게된 점

- 맨 처음 단순 점화식을 통해 문제를 풀어보려고 했지만 출력초과가 나왔다. 아마 출력값이 비정상적으로 커졌기 때문인 것 같다.

- 그래서 우선순위 큐를 검색했고 제거하는 경우 자동적으로 min 값을 pop한다는 것을 알았다.

- 문제는 의외로 간단하게 풀렸다.

 

 

참고 사이트

- 우선순위 큐 : https://johnyejin.tistory.com/72

[Python]우선순위큐(PriorityQueue) 라이브러리

 

-