[Baekjoon] 1715번 : 카드 정렬하기 python

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

1715번: 카드 정렬하기

 

설계 방법

비교 횟수가 가장 작으려면 가장 작은 값들부터 먼저 계산해야 한다.

단 하나의 값이 남을 때까지 가장 작은 값 2개를 계산, 추가 그리고 저장을 반복한다.

일반적인 배열로 처리할 경우 시간 초과가 발생한다.

정렬하는 과정을 우선순위 큐에 맡겨주면 해결 

 

코드

시간초과 코드

import sys
input = sys.stdin.readline

n = int(input())

card = []
for i in range(n):
  card.append(int(input()))

sub = 0
card.sort()
for i in range(1,n):
  sub += sum(card[:i+1])

print(sub)

 

틀렸습니다..

import sys
input = sys.stdin.readline

n = int(input())

card = []
for i in range(n):
  card.append(int(input()))

sub = [0] * (n+1)
card.sort()

sub[0] = card[0]
for i in range(1,n):
  sub[i] = sub[i-1] + card[i]

print(sum(sub[1:]))

 

🔫 정답 코드 

우선순위큐로 푸는거였음 ㅠㅠ 

import heapq
import sys
input = sys.stdin.readline

n = int(input())
card = [int(input()) for _ in range(n)]
heapq.heapify(card)

c = 0
s = 0

while len(card) > 1:
  n1 = heapq.heappop(card)
  n2 = heapq.heappop(card)
  c = n1 + n2
  s += c
  heapq.heappush(card, c)

print(s)