카드 정렬하기 - 백준 1715번

카드를 묶는 순서를 우선순위 큐로 생각하여 문제를 해결한다.

5 묶음의 카드가 10, 20, 30, 40, 50 장 있다고 생각해 보자

가장 작은 수 2개를 묶은 뒤 비교횟수에 더하고 다시 가장 작은 수 2개를 묶은 뒤 비교횟수에 더하는 행위를 카드 묶음이 1개가 남을 때 까지 반복해준다.

1. 10 20 30 40 50 (묶기) result : 0
2. 30 30 40 50 (묶기) result : 0 + 30
3. 60 40 50 (묶기) result : 30 + 60
4. 60 90 (묶기) result : 90 + 90
5. 150 (묶기) result : 180 + 150
6. 150 (완료) result : 330

파이썬의 heapq를 이용하면 이 과정 그대로 진행해주면 되고, 배열만 이용하여 문제를 해결하게 되면 3번째 부분에서 정렬을 해주면된다. 하지만 배열을 이용하면 백준 컴파일러에서는 시간초과가 뜬다.

 

# 배열만 사용
t = int(input())
arr = []
for _ in range(t):
    card = int(input())
    arr.append(card)

if t == 1:
    print(0)
else:


    sum = 0

    while len(arr) > 1:
        arr.sort()
        plus = arr[0] + arr[1]
        sum += plus
        arr.pop(0)
        arr.pop(0)
        arr.append(plus)

    print(sum)

 

# heapq 우선순위 큐 사용
import heapq
arr = []
sum = 0
t = int(input())
for _ in range(t):
    card = int(input())
    heapq.heappush(arr,card)
if t==1:
    print(0)
else:
    while len(arr) > 1:
        plus = heapq.heappop(arr) + heapq.heappop(arr)
        sum += plus
        heapq.heappush(arr, plus)
    print(sum)

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

1715번: 카드 정렬하기