백준 1715 - 카드 정렬하기

문제 설명

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 카드 더미 A와 B를 정렬하는데 A+B번의 비교가 필요하다.

N개의 카드더미가 주어졌을 때 비교횟수를 최소한으로 하여 정렬할 때의 비교 횟수를 출력해야 한다.

 

문제의 룰은 간단하다.

가장 작은 두 개의 카드 더미를 선택해 하나로 합쳐질 때까지 합치면 된다.

핵심은 가장 작은 두 개의 카드 더미를 구하는 것이다.

간단하게는 정렬한 뒤 앞에서 부터 두 개를 뺀 뒤 다시 정렬하면 된다고 생각할 수 있다.

하지만, 논리적으로는 맞지만 시간초과에 걸린다.

그렇다면 정렬없이 인서트소트와 같은 방식으로 앞에서부터 비교하며 N번만에 자신의 위치를 고르면 되지 않겠느냐고 생각할 수 있다.

하지만, 마찬가지로 시간초과에 걸린다.

 

그래서 생각한 방법은 결과를 저장하는 배열을 하나 더 만드는 것이다.

결과를 저장하는 배열에 가장 작은 두 개의 합을 저장하는 식으로 진행한다.

만약 결과 배열이 비어있다면 카드 더미에서 두 개를 고르고 반대의 경우에는 결과 배열에서 두 개를 고른다.

만약, 둘 다 비어있지 않은 경우에는 둘을 비교하며 작은 수 두 개를 고른다.

이러한 논리가 성립하는 이유는 정렬을 했기 때문이다.

결과를 저장하는 배열은 카드 더미에서 고른 가장 작은 두 수이기 때문에 그보다 크다는 것이 항상 보장된다.

또한, 나중에 저장된 결과가 먼저 저장된 결과보다 크다는 것을 보장한다.

즉, 따로 정렬할 필요가 없다.

 

한 가지 단점이 있는데 조건문이 조금 지저분하다.

결과를 저장하는 배열과 카드 더미를 저장하는 배열의 요소 수를 검사하는 부분이 여러 번 들어가기 때문이다.

 

이러한 조건문의 반복이 싫고 깔끔한 코드를 원한다면 우선순위 큐를 사용하는 것도 좋은 방법이다.

하지만, 앞에서 설명한 방법이 조금 더 시간이 빠르다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N;

    deque<long long> cards(N);
    deque<long long> temp;
    for (int i = 0; i < N; i++)
    {
        cin >> cards[i];
    }

    if (N == 1)
    {
        cout << 0;
        return 0;
    }

    sort(cards.begin(), cards.end());

    long long ans = 0;

    while (cards.size() + temp.size() > 1)
    {
        long long a;
        long long b;

        //find a
        if (temp.empty())
        {
            a = cards.front();
            cards.pop_front();
        }
        else
        {
            if (cards.empty())
            {
                a = temp.front();
                temp.pop_front();
            }
            else if (temp.front() < cards.front())
            {
                a = temp.front();
                temp.pop_front();
            }
            else
            {
                a = cards.front();
                cards.pop_front();
            }
        }

        //find b
        if (temp.empty())
        {
            b = cards.front();
            cards.pop_front();
        }
        else
        {
            if (cards.empty())
            {
                b = temp.front();
                temp.pop_front();
            }
            else if (temp.front() < cards.front())
            {
                b = temp.front();
                temp.pop_front();
            }
            else
            {
                b = cards.front();
                cards.pop_front();
            }
        }

        ans += a + b;
        temp.push_back(a + b);
    }

    cout << ans;

    return 0;
}

---