from heapq import *
N = int(input())
nums = [*map(int,input().split())]
hq = sorted((3*nums[i],nums[i],2) for i in range(N))
S = sum(nums)
for i in range(N-2):
w,n,x = heappop(hq)
S += w
heappush(hq,((x*2+1)*n,n,x+1))
print(S if N!=1 else 0)우선순위 큐를 이용해서 해결하였다.
처음에는 단순한 MST 문제라고 생각했다. 하지만 어떤 노드와 어떤 노드가 연결되는지가 전혀 중요하지 않고 각 노드가 연결된 개수만 고려해주면 되기 때문에 그리디하게 해결할 수 있다.
풀이를 설명하면,
1. 일단 모든 노드가 전부 한번씩 연결되어있다고 가정, S를 인원수의 합으로 둔다.
2. 모든 노드를 연결하기 위해선 N-1개의 간선이 필요하다. 각 간선은 두 개의 노드를 연결하므로 총 연결수는 2N-2개이다. 1에서 N개의 연결을 했기 때문에 N-2번 추가로 연결해주면 된다.
3. 만약 현재 노드의 인원수가 n명, 연결횟수가 x번이라면, 다음 연결을 위해 필요한 비용은 (x*2+1)*n이다. (왜냐하면 (x+1)^2-x^2 = x*2+1이므로)
4. 우선순위 큐에 다음 연결을 위해 필요한 비용을 기준으로 넣는다.
5. 비용이 가장 작은 순으로 연결하고, 연결이 끝나면 다음 연결을 위해 필요한 비용을 갱신해서 우선순위 큐에 다시 넣는다.
6. N-2번 연결을 해주고 비용을 출력한다. (주의: 이때 N=1인 경우 0을 출력한다)
N이 1인 경우 연결을 전혀 할 필요가 없기 때문에 주의해야한다.
여담) 이 문제의 숏코딩 순위 1위가 되었다.
