C++에서 스틱을 연결하기 위한 최소 비용

양의 정수 길이를 가진 막대기가 있다고 가정합니다. X + Y의 비용을 지불하면 길이가 X와 Y인 막대 두 개를 하나의 막대로 연결할 수 있습니다. 이것은 막대가 하나 남을 때까지 수행됩니다. 이런 식으로 주어진 모든 스틱을 하나의 스틱으로 연결하는 최소 비용을 찾아야 합니다. 따라서 스택이 [2,4,3]이면 출력은 14가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

최대 힙 우선순위 큐 pq 정의
s의 모든 요소를 pq에 삽입
ans :=0
pq에 둘 이상의 요소가 있는 동안
- temp :=큐의 맨 위, pq에서 맨 위 삭제
- temp :=temp + pq의 최상위 요소, pq에서 삭제
- ans :=ans + temp
- pq에 temp 삽입
반환

예(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int connectSticks(vector<int>& s) {
      priority_queue <int, vector<int>, greater<int> > pq;
      for(int i =0;i<s.size();i++)pq.push(s[i]);
      int ans = 0;
      while(pq.size()>1){
         int temp = pq.top();
         pq.pop();
         temp += pq.top();
         pq.pop();
         ans+=temp;
         pq.push(temp);
      }
      return ans;
   }
};
main(){
   vector<int> v = {2,4,3};
   Solution ob;
   cout <<ob.connectSticks(v);
}

입력

[2,4,3]