1. 문제 설명

Fix Wiring

2. 문제 분석

MST는 주어진 모든 간선 비용 페어 중 노드 개수 - 1개만큼을 최솟값을 구해 더하면 된다. 이렇게 정렬된 비용 리스트를 통해 특정 노드 페어에서 최소 스패닝 트리를 구했을 때 그 값이 최대한 경우 역시 구할 수 있다(바로 옆에 있을 때에만 연결시킬 수 있다).

3. 나의 풀이

import sys
import heapq

n = int(sys.stdin.readline().rstrip())
costs = list(map(int, sys.stdin.readline().rstrip().split()))
costs.sort()

min_answer = 0
for i in range(n-1):
    min_answer += costs[i]

max_answer = 0
cnt = 0

for i in range(1, n):
    for j in range(i-1, -1, -1):
        if (i == j+1):
            max_answer += costs[cnt]
        cnt += 1

print(min_answer, max_answer)