[알고리즘/백준] 11715_카드 정렬하기

알고리즘

가장 작은 값끼리 먼저 더해야 최소 비용으로 카드를 묶을 수 있다.
힙 구조(priority_queue)를 사용

입력 값 : 1, 2, 3, 4, 5
자료구조 : priority_queue <int, vector, greater> pq;

1 + 2 = 3을 answer 변수에 더한 후 그 값을 다시 우선순위 큐에 넣는다.
answer = 3

3 + 3 = 6을 answer 변수에 더한 후 그 값을 다시 우선순위 큐에 넣는다.
answer = 9

4 + 5 = 9을 answer 변수에 더한 후 그 값을 다시 우선순위 큐에 넣는다.
answer = 18

6 + 6 = 12를 answer 변수에 더한 후 그 값을 다시 우선순위 큐에 넣는다.
answer = 30

9 + 12 = 21을 answer 변수에 더한다.
answer = 51
우선순위 큐가 비었을 때 반복문을 빠져나온다.

소스코드

#include <iostream>
#include <queue>
using namespace std;

int main(){
  int n, answer = 0;
  priority_queue<int, vector<int>, greater<int>> pq;
  scanf("%d", &n);
  for(int i = 0 ; i<n ; i++){
      int num;
      cin >> num;
      pq.push(num);
  }

  while(!pq.empty() && n>1){
      int x=0, y=0;
      x= pq.top();
      pq.pop();
      
      y = pq.top();
      pq.pop();
      
      int z = x+y;
      answer += z;
      if(pq.empty()){
          break;
      }
      pq.push(z);
      
  }
  printf("%d", answer);
  return 0;
}

실행 결과 : 51