백준 1715 파이썬 코드 답안

백준 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보다 작거나 같은 양의 정수이다.

출력

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

 

문제풀이

이 문제를 풀기 위해서는 예시에서 원하는 것이 무엇인지를 정확히 파악하는 것이 먼저다. 10,20,40이라는 카드가 있다고 가정을 하자. 이 때 카드를 비교하는 방법을 먼저 이해를 해야하는데... 10,20번의 카드 묶음을 비교한다면 10+20의 비교 횟수가 필요하다고 한다.

10,20을 비교하게 되면, 이 카드를 비교하는 것만으로 30의 값을 가지게 된다. 그럼 이 카드는 한 묶음으로 칠 수 있고, 30짜리 카드와 40짜리 카드를 비교하는 경우만 남는다. 그래서 30+40을 다시 한 묶음으로 만들기 위해서는 70번의 비교횟수가 필요하다. 따라서 10,20,40을 비교할 때는 위와 같은 방법으로 했을 때 100번의 비교횟수가 필요하다.

그런데 비교는 저렇게만 할 수 있는 것은 아니다. 먼저 10과 40의 카드를 비교하면, 50의 비교횟수가 필요하고 50개의 카드 묶음이 탄생한다. 그 후, 50과 20의 카드를 비교해서 70의 카드 묶음을 만들 수 있다. 이 경우 (10+40) + (50 + 20)의 비교횟수가 필요하며, 이 때는 120번의 비교횟수가 필요하다.

문제는 최소 비교횟수를 찾는 것인데, 위의 두 예시를 볼 경우 항상 작은 카드 숫자를 가진 카드 2장을 뽑아서 비교하고, 추가하는 연산을 반복해야한다는 것을 인지하게 된다. 

이 문제는 내가 생각하기에는 두 가지 방법으로 접근이 가능하다. 
첫번째는 리스트 자료구조를 활용하는 것이다. 숫자가 큰 순으로 정리를 해서, 뒷쪽의 두 개의 값만 뽑아내서 계산을 하고 다시 리스트에 넣고, 정렬을 반복하는 방법이다.

while 1 :
	if len(my_list) >= 2 : 
    	a = my_list.pop()
        b = my_list.pop()
        my_sum += (a+b)
        my_list.append(a+b)
        my_list = soretd(my_list, reverse = T)
    elif len(my_list) == 1 : 
    	break

핵심 연산 코드는 위와 같을텐데, 이 경우 주어진 원소의 갯수가 n개라고 가정했을 때 시간 복잡도를 유추해보면 O(n^2 * logn)이 나온다. n이 100,000이라는 것을 가정하면 가뿐하게 1억의 값이 넘기 때문에 시간초과에 봉착할 수 밖에 없다.

두번째, 가장 작은 값만을 뽑아서 계속 더해야 한다는 것에 착안하면 힙이라는 구조를 사용할 수 있다. 힙은 최소힙, 최대힙으로 나타내며, 파이썬의 heapq 모듈은 최소힙으로 구현이 되어있다. 즉, 힙이라는 자료구조를 사용해서 항상 최소값만 뽑아내는 것을 반복하는 식으로 계산할 수 있다.

이렇게 코드를 짤 경우, 시간복잡도는 n*logn으로 예상이 되기 때문에 시간초과가 발생하지 않을 것이라고 생각할 수 있다. heapq 모듈을 사용한 코드는 아래와 같다. 

import sys
import heapq

my_list = []
for i in range(int(sys.stdin.readline().rstrip())) :
    my_list.append(int(sys.stdin.readline().rstrip()))
heapq.heapify(my_list)
answer = 0
while len(my_list) != 1 :
    a = heapq.heappop(my_list)
    b = heapq.heappop(my_list)
    heapq.heappush(my_list,a+b)
    answer += (a+b)
    if len(my_list) == 1 :
        break

print(answer)