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

1715번: 카드 정렬하기 (acmicpc.net)

1715번: 카드 정렬하기

문제

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

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

예제 입력 1 복사

3
10
20
40

예제 출력 1 복사

100

 

# Code

import sys
import heapq

input = sys.stdin.readline

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

result = 0

if len(cards)==1:
    print(result)

else:
    for i in range(n-1): # 2개씩 꺼내기 떄문에 n-1
        previous = heapq.heappop(cards)
        current = heapq.heappop(cards)

        result += previous + current
        heapq.heappush(cards,previous + current)
    
    print(result)

 

# Comment

sort를 써서 풀어보려고 했는데 .... 계속 틀렸다고 해서 ^^.... 알고리즘 자체는 그냥 오름차순 정렬하고 작은 것부터 두개씩 묶어서 누적해서 더해주면 되는 건데 구현이 잘 안돼서 풀이를 참고했다.. 우선순위 큐를 쓰면 되는 거였다 ^-^!!

heapq를 이용해서 우선순위 큐를 구현한다.  우선순위큐는 자동으로 작은 것부터 pop해주기 때문에 이 문제를 푸는데 유용하다.  previous 변수와 current 변수에 각각 가장 작은 값들을 넣고 더해준 다음 누적해서 더해야 하기 때문에 더한 값을 다시 heapq에 넣어주는 것을 반복하면 된다. 문제의 예시로 설명해보면,

10 20 40  previous = 10, current = 20 , result = 30 이때 previous와 current를 더한 값을 다시 heapq에 넣어주면,
 
  30 40  previous = 30, current = 40, result = 100 이렇게 된다.

우선순위 큐 개념을 다시금 다질 수 있었다.. 다음번엔 잘 떠올리고 적용해 볼 수 있길..