Baekjoon 15903: 카드 합체 놀이

문제 설명

• 문제 링크
• Algorithm: Greedy, Priority Queue
• 난이도: Silver 1 ('24. 9. 2.)
• 출처: 랜덤 마라톤 코스 12

풀이

• 가정: 전체 카드의 합을 $S$라 하자
• 추론: 한 번의 과정이 끝나면 $S - x - y + (x + y) + (x + y) = S + (x + y)$ 이다.
• 결론: $m$번의 과정을 끝낸 뒤 $S$가 가장 작아지려면 한 번의 과정 때 선택하는 $(x + y)$가 가장 작아야한다.
  • 즉, 한 번의 과정에서 가장 작은 x, y를 선택한 뒤 더해준다!
  • 매 과정마다 값이 바뀌고, 바뀐 배열에서 2개의 작은 값들을 찾아야 하니 우선순위 큐로 과정을 구현한다.

코드

// Baekjoon15903.cpp
#include <iostream>

#include <queue>
#include <vector>

using namespace std;

using ll = long long;

struct compare {
    bool operator()(ll a, ll b) {
        return a > b;
    }
};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

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

    ll sum = 0LL;
    priority_queue<ll, vector<ll>, compare> pq;
    for (int i = 0; i < n; i++) {
        ll num;
        cin >> num;

        sum += num;

        pq.push(num);
    }

    while (m--) {
        ll small1 = pq.top(); pq.pop();
        ll small2 = pq.top(); pq.pop();

        ll twoSum = small1 + small2;

        sum += twoSum;

        pq.push(twoSum);
        pq.push(twoSum); 
    }

    cout << sum << '\n';

    return 0;
}

잡담

• 사실 저렇게 수식 쓰고 그랬지만 생각할 때는 작은거 2개 선택하면 무조건 될 듯이라 생각했다!
• 옛날에 풀었지만 요즘 다른 일들이 많다보니 이제 올린다 ㅎ 앞으로 밀린 문제가 많으니 부지런히 올려보겠다!