[백준] 1715번 카드 정렬하기 (C++)

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

 

 

이 문제는 백준 파일 합치기 문제(13975번)와 굉장히 유사한 문제이다.

정렬된 카드의 수치를 입력받고 그 값들을 2개씩 더하여 최소한의 비교 수치를 계산하는 문제이다.

 

 

즉 최소한의 비교수치를 알기 위해서 정렬된 카드에서 가장 작은 숫자 2개를 더하고 생성된 카드를 다시 전체에서 비교하여 가장 작은 2개를 더하여 계속해서 비교한다. -> 최소힙 사용

 

정답 코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

int dx[] = {0, 1, -1, 0, 1, -1, -1, 1};
int dy[] = {1, 0, 0, -1, -1, 1, -1, 1};
int N;
priority_queue<int, vector<int>, greater<int>> pq;

void solve() {
    int result = 0;

    while(pq.size() != 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        int tmp = a + b;
        result += tmp;
        pq.push(tmp);
    }
    
    cout << result;
}

void input() {
    cin >> N;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}

 

 

회고록

이전에 풀어봤던 문제와 굉장히 유사했던 문제여서 아이디어가 바로 생각날 수 있었다.