백준 15903번 [카드 합체 놀이](C++) -yes6686- 티스토리

백준 문제 풀이: 15903 (카드 합체 놀이)

---

문제 링크: https://www.acmicpc.net/problem/15903

문제 설명:

N개의 카드를 가진 카드 묶음이 주어집니다. 이 중 가장 숫자가 작은 두 카드를 골라 합쳐 두 장 모두 그 합으로 바꾸는 작업을 M번 반복한 뒤, 모든 카드의 합을 출력하는 문제입니다.

가장 작은 두 수를 반복적으로 찾아야 하므로, 우선순위 큐(Min-Heap)를 사용한 그리디 알고리즘이 적합합니다.

---

문제 해결 코드

// 우선순위 큐를 활용한 최적화된 풀이
#include <iostream>
#include <queue>
using namespace std;

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

    int n, m;
    cin >> n >> m;

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

    while (m--) {
        long long a = pq.top(); pq.pop();
        long long b = pq.top(); pq.pop();
        long long sum = a + b;
        pq.push(sum);
        pq.push(sum);
    }

    long long result = 0;
    while (!pq.empty()) {
        result += pq.top();
        pq.pop();
    }

    cout << result << '\n';
}

---

코드 설명

그리디 전략과 우선순위 큐를 활용하여 반복적으로 가장 작은 두 수를 합칩니다.

• 핵심 알고리즘: 우선순위 큐(Min-Heap)를 사용한 그리디 알고리즘
• 구현 세부사항:
  • 매번 가장 작은 두 수를 pop하여 더하고, 그 합을 두 번 push합니다.
  • priority_queue<T, vector<T>, greater<>>는 최소 힙을 구현합니다.
• 시간 복잡도 분석:
  • 각 연산은 O(log n)
  • M번 연산하므로 전체 시간 복잡도: O(m log n)

---

결과

예시 입력:

3 1
3 2 6

예시 출력:

16

정렬 기반 반복보다 훨씬 효율적인 우선순위 큐 기반 접근으로 문제를 해결했습니다.
다른 풀이 방식이나 반례가 있다면 댓글로 공유해주세요!