[백준 1715] 카드 정렬하기 (C#, C++) - soo:bak

문제 링크

1715번 - 카드 정렬하기

설명

여러 카드 묶음을 하나로 합칠 때, 두 묶음을 합치는 비용은 두 묶음의 카드 수 합입니다. 모든 카드를 하나로 합치는 데 필요한 최소 비교 횟수를 구하는 문제입니다.

접근법

전체 비교 횟수를 최소화하려면 항상 가장 작은 두 묶음부터 합쳐야 합니다. 큰 묶음을 먼저 합치면 그 비용이 이후에도 계속 누적되기 때문입니다.

가장 작은 두 묶음을 효율적으로 찾기 위해 최소 힙을 사용합니다. 힙에서 가장 작은 두 값을 꺼내 합친 뒤, 그 합을 답에 더하고 다시 힙에 넣습니다. 이 과정을 힙에 원소가 하나 남을 때까지 반복합니다.

묶음이 하나뿐이면 합칠 필요가 없으므로 답은 0입니다.

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static void Main(string[] args) {
      var n = int.Parse(Console.ReadLine()!);
      if (n == 1) {
        Console.WriteLine(0);
        return;
      }

      var pq = new PriorityQueue<int, int>();
      for (var i = 0; i < n; i++) {
        var v = int.Parse(Console.ReadLine()!);
        pq.Enqueue(v, v);
      }

      var ans = 0L;
      while (pq.Count > 1) {
        pq.TryDequeue(out var a, out _);
        pq.TryDequeue(out var b, out _);
        var sum = a + b;
        ans += sum;
        pq.Enqueue(sum, sum);
      }

      Console.WriteLine(ans);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n; cin >> n;
  if (n == 1) {
    cout << 0 << "\n";
    return 0;
  }

  priority_queue<int, vi, greater<int>> pq;
  for (int i = 0; i < n; i++) {
    int v; cin >> v;
    pq.push(v);
  }

  ll ans = 0;
  while (pq.size() > 1) {
    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();
    int sum = a + b;
    ans += sum;
    pq.push(sum);
  }

  cout << ans << "\n";

  return 0;
}