[BOJ 15903] 카드 합체 놀이

문제

카드 합체 놀이

https://www.acmicpc.net/problem/15903

 

 

풀이

설명

규칙에 따라 만들 수 있는 가장 작은 점수를 구하는 문제입니다.

 

규칙은 다음과 같습니다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산합니다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 씁니다.
3. 1, 2번을 m번 반복한 후, 모든 카드에 쓰여있는 수의 합이 점수가 됩니다.

 

최소 힙을 사용해 해결할 수 있습니다.

js의 경우, BigInt를 사용해야 합니다.

 

예시 코드

function solution() {
  const [n, m] = input().split(" ").map(Number);
  const cards = input().split(" ").map(Number);
  const heap = new MinHeap();
  for (const card of cards) {
    heap.insert(BigInt(card));
  }

  for (let i = 0; i < m; i++) {
    const x = heap.remove();
    const y = heap.remove();
    const newVal = BigInt(x) + BigInt(y);
    heap.insert(newVal);
    heap.insert(newVal);
  }

  let sum = BigInt(0);
  for (let i = 0; i < n; i++) {
    sum += heap.remove();
  }

  return sum.toString();
}