[Algorithm🧬] 최소 비용으로 포장 다시 하기

문제

처음에는 파스칼의 삼각형이라고 생각했는데 전혀 아니었다.
그냥 정렬해서 앞에 두개 더하고, 그 더한 결과물을 배열에 다시 오름차순 맞게 넣어주고
그거랑 그 다음 큰거 더하고... 이렇게 해야하는데
배열에 다시 넣으려면... 전체 탐색 생각했는데 시간 복잡도 때문에 heap 을 이용해야 하는거였다.

import sys
import heapq

n = int(sys.stdin.readline())
candies = list(map(int, sys.stdin.readline().split()))

sum = 0

candyheap = []
for i in range(n):
    heapq.heappush(candyheap, candies[i])

for _ in range(n - 1):
    n1 = heapq.heappop(candyheap)
    n2 = heapq.heappop(candyheap)

    sum += (n1 + n2)
    heapq.heappush(candyheap, n1 + n2)

print(sum)

heapq 이용법 다 잊어버려서 당황했다.....

다시 푼 것. sort 이용 -> 이것도 결국 n log n 이라 상관은 없을듯.

import sys

def Input_Data():
	readl = sys.stdin.readline
	N = int(readl())
	package = list(map(int,readl().split()))
	return N, package


sol = 0
# 입력받는 부분
N, package = Input_Data()

# 여기서부터 작성

for i in range(N - 1):
	package.sort()
	first = package.pop(0)
	package[0] += first
	sol += package[0]

# 출력하는 부분
print(sol)