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

골드4 문제이며, 제한 시간은 2초이다.

문제

해결 과정

처음에 이 문제를 딱 봤을 때는 단순히 정렬 후 앞에서부터 조건에 맞게 더하면 될 줄 알았다.

이 방법의 문제점은 작은 수 두 개를 더한 값과 그 다음 수를 더한 결과가 다른 수 두 개를 더한 값보다 커질 수 있다는 점이다.

이렇게 되면 더 큰 수와 다음 수를 더하게 되므로 덜 효율적인 방법이 되버린다.

따라서 우선순위 큐를 이용해 더한 결과도 다시 우선순위 큐에 넣어서 현재 가장 작은 값 두 개를 더하는 방식으로 문제를 해결했다.

1. 입력받은 수를 우선순위 큐에 넣는다.
2. 두 번의 pop을 통해 현재 가장 작은 값 두 개를 추출한다.
3. result에 두 수의 합을 더해준다.
4. 두 수의 합을 다시 우선순위 큐에 넣어준다.
5. 우선순위 큐의 길이가 1이 되면 종료한다.

풀이

import sys, heapq
input = sys.stdin.readline

n = int(input())
cards = []
for _ in range(n):
  heapq.heappush(cards, int(input()))

result = 0
if len(cards) == 1:
  print(0)
else:
  while len(cards) > 1:
    num1 = heapq.heappop(cards)
    num2 = heapq.heappop(cards)
    result += num1 + num2
    heapq.heappush(cards, num1 + num2)
  print(result)

처음에 제출했을 때 95%에서 자꾸 틀렸는데 그 이유는 입력된 값이 한 개일 때, 비교 대상이 없으므로 0을 출력해야 하는데 바보같이 입력된 값을 출력했었다...