[백준 1715] 카드 정렬하기

카드 정렬하기

문제설명

총 카드 묶음의 수를 입력 받은 뒤, 각 카드의 수를 입력 받는다. 이때 카드를 확인하는 수를 A+B라고 한다. 가장 적은 수의 카드를 확인하는 경우의 수를 출력시킨다.

알고리즘

1. 카드 묶음의 수와 각 카드 묶음 당 카드의 수를 입력 받는다.
2. priority_queue를 사용하여 수가 입력되면 자동으로 오름차순으로 정렬되도록 한다.
3. 큐에서 가장 앞에있는 (가장 작은 두 값) 두 값을 꺼내서 ans 변수에 더한 값을 넣는다.
4. 다시 더한 값을 queue 에 넣고, 원래의 두 값은 지운다.
5. queue에 남은 수가 1개가 되면 반복을 멈추고 나와서 ans의 값을 출력한다.

---

#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    priority_queue <int,vector<int>, greater<int>>q; //오름차순으로 정렬하는 우선순위 큐
    int ans = 0;

    int N;
    cin >> N;

    for (int i = 0; i < N; i++)//숫자 입력
    {
        int temp;
        cin >> temp;
        q.push(temp);
    }

    while(q.size()!=1)// 크기가 1이 되면 결과 출력 
    {
        int a = q.top();//첫 값 빼기
        q.pop();
        int b = q.top();//두번 째 값 빼기
        q.pop();
        q.push(a + b);//더해서 다시 queue 에 넣기 
        ans += a + b;//결과 값에 더해주기
    }

    cout << ans << "\n";

    return 0;
}

고찰

이번 문제는 priority_queue의 특징을 알면 쉽게 풀 수 있는 문제였다.
우선순위 큐를 사용하면 값이 들어올 때 마다 알아서 정렬 된다는 장점이 있다.
따라서 가장 작은 두 수 끼리 더해서 최소한을 구한다라는 이 문제의 핵심을 가장 간단하게 구현할 수 있다.