백준/구현

# 1715 카드 정렬하기

bright_code 2021. 4. 10. 23:07
728x90
반응형

www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

import heapq
import sys 
input = sys.stdin.readline 

n = int(input())
data = [] 
for i in range(n) : data.append(int(input()))
heapq.heapify(data)
result = 0 

while data:
  first = heapq.heappop(data)

  if len(data)<=0:   # 원소가 1개 이하일 때 
    break 
  
  second = heapq.heappop(data)
  heapq.heappush(data, first+second )
  result += first + second 

for i in data : 
  result += i 

print(result)

 

처음 더한 값들이 반복되어 더해지므로, 가장 작은 값부터 더해야한다. 

우선순위 큐를 이용해서 작은 값을 꺼낸다. 

728x90
반응형