[백준 15903] 카드 합체 놀이 (C#, C++) - soo:bak

문제 링크

15903번 - 카드 합체 놀이

설명

가장 작은 두 카드를 골라 합을 두 장에 덮어쓰는 과정을 m번 반복한 뒤 모든 카드의 합을 구하는 문제입니다.

접근법

가장 작은 두 값을 반복해서 뽑아야 하므로 최소 힙을 사용합니다.

매번 두 값을 꺼내 합한 뒤 그 합을 두 번 다시 넣습니다.

이를 m번 수행한 후, 힙에 남은 값을 모두 더해 출력합니다.

Code

C#

using System;
using System.Collections.Generic;

class Program {
  static void Main() {
    var nm = Array.ConvertAll(Console.ReadLine()!.Split(), int.Parse);
    var n = nm[0];
    var m = nm[1];
    var vals = Array.ConvertAll(Console.ReadLine()!.Split(), long.Parse);
    var pq = new PriorityQueue<long, long>();
    foreach (var x in vals)
      pq.Enqueue(x, x);

    for (var i = 0; i < m; i++) {
      pq.TryDequeue(out var a, out _);
      pq.TryDequeue(out var b, out _);
      var sum = a + b;
      pq.Enqueue(sum, sum);
      pq.Enqueue(sum, sum);
    }

    var ans = 0L;
    while (pq.Count > 0) {
      pq.TryDequeue(out var x, out _);
      ans += x;
    }
    Console.WriteLine(ans);
  }
}

C++

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

typedef long long ll;

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

  int n, m; 
  if (!(cin >> n >> m)) return 0;
  priority_queue<ll, vector<ll>, greater<ll>> pq;
  for (int i = 0; i < n; i++) {
    ll x; cin >> x;
    pq.push(x);
  }

  for (int i = 0; i < m; i++) {
    ll a = pq.top(); pq.pop();
    ll b = pq.top(); pq.pop();
    ll sum = a + b;
    pq.push(sum);
    pq.push(sum);
  }

  ll ans = 0;
  while (!pq.empty()) {
    ans += pq.top();
    pq.pop();
  }
  cout << ans << "\n";

  return 0;
}