[BOJ - 1715] 카드 정렬하기(C++)

  문제

 

  접근 방법

항상 가장 작은 두 묶음을 선택하는 방법을 사용해야 함 -> 최소 힙으로 접근하기로 결정

 

 

  기존 코드

#include <iostream>
#include <queue>

using namespace std;

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

    priority_queue<int, vector<int>, greater<int>> q;

    for (int i = 0; i < N; i++) {
        int card;
        cin >> card;

        q.push(card);
    }


    int result = 0;
    while (q.size() > 1) {
        int t = q.top();
        q.pop();

        t += q.top();
        q.pop();

        result += t;

        q.push(t);
    }

    cout << result;

    return 0;
}

 

 

  개선한 코드

#include <iostream>
#include <queue>

using namespace std;

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

    int N;
    cin >> N;

    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < N; i++) {
        int card;
        cin >> card;
        pq.push(card);
    }

    int total = 0;

    while (pq.size() > 1) {
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();

        int sum = first + second;
        total += sum;

        pq.push(sum);
    }

    cout << total << "\n";

    return 0;
}

 

 가독성 좋게 코드를 작성하자는 교훈....

  링크

1715번: 카드 정렬하기