< 백준 BaekJoon : 1715번 카드 정렬하기 > C++

<< 문제 >>

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

1715번: 카드 정렬하기

 

수식이 간단해서 어렵지 않게 보일 수 있는데, 

 

핵심적으로 생각해야 할 것은 합쳐서 만들어낸 묶음이 다른 묶음보다 커질 수 있다는 것이다.

그렇다는 것은 묶음을 합칠 때, 해당 묶음을 사용해서는 안된다는 것.

 

작은 것을 꺼내는건 PQ를 이용하면 쉽게 활용할 수 있다. 

 

 

<< 코드 >>

#include <iostream>
#include <queue>
using namespace std;


/// 핵심은 합쳐서 만들어진 묶음이 다른 묶음보다 클 수 있다는 점
/// 다 PQ에 때려넣고, 그 중 작은 두 개를 찾아 비교한다.

int main() {
    int InputNum;
    cin >> InputNum;

    // PQ는 기본적으로 내림차순이기 때문에 -를 붙여 오름차순으로 사용
    priority_queue<int> pq;
    for (int i = 0; i < InputNum; i++) {
        int n;
        cin >> n;
        pq.push(-n);
    }
    
    if (InputNum == 1) {
        cout << 0;
        return 0;
    }


    long long result = 0;
    int arg1, arg2;
    while (1) {
        arg1 = -pq.top();
        pq.pop();
        arg2 = -pq.top();
        pq.pop();

        result += (arg1 + arg2);

        if (pq.empty()) {
            break;
        }
        pq.push(-(arg1 + arg2));
    }
    cout << result;
    return 0;
}

 

 

<< GitHub >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Gold/1715.%E2%80%85%EC%B9%B4%EB%93%9C%E2%80%85%EC%A0%95%EB%A0%AC%ED%95%98%EA%B8%B0

StudyAlgorithm_Part2/백준/Gold/1715. 카드 정렬하기 at main · J2on/StudyAlgorithm_Part2