백준 1715번 카드 정렬하기

🔒[문제 url]

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

🔑알고리즘

각각 $a,b,c$장씩 묶인 카드를 합친다고 가정하자.
1. $a$와 $b$를 먼저 합칠 경우 : $(a+b)+(a+b+c)$
= $2(a+b)+c$
2. $a$와 $c$를 먼저 합칠 경우 : $(a+c)+(a+c+b)$
= $2(a+c)+b$
3. $b$와 $c$를 먼저 합칠 경우 : $(b+c)+(b+c+a)$
= $2(b+c)+a$
위 예시를 통해, 먼저 합치는 수일수록 여러번 더해짐을 알 수 있다.

• 즉, 가장 작은 두 수부터 합쳐나간 것이 최소 비교 횟수가 된다.
  • 따라서, 오름차순의 priority queue에 모든 카드를 삽입한 뒤, top()에서 두 개의 원소를 pop하여 더한 뒤 다시 priority queue에 push를 반복한다.

🐾부분 코드

생략한다.

🪄전체 코드

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

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

void INPUT()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int size; cin >> size;
        q.push(size);
    }
}

void SOLVE()
{
    int ans = 0;
    while (!q.empty())
    {
    	//더이상 합칠 수 없다면 종료
        if(q.size() == 1) break;

		//가장 작은 묶음
        int first = q.top(); q.pop();
        //두번째로 작은 묶음
        int second = q.top(); q.pop();

		//합친 후 queue에 push
        ans += first + second;
        q.push(first + second);
    }
    cout << ans;
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

pq만 잘 활용하면 어렵지 않은 문제.
필요한 아이디어와 배경지식을 따져봤을 때 Gold4까지 올라올 난이도는 아닌 것같다.