최소 비용으로 N개의 로프 연결하기 – 힙(Heap) 알고리즘 풀이

주어진 길이를 가진 N개의 로프가 있습니다. 이 로프들을 모두 하나로 연결해야 하는데, 두 로프를 연결할 때 드는 비용은 두 로프 길이의 합입니다. 목표는 N개의 로프를 최소 비용으로 모두 연결하는 것입니다.

이 문제는 힙 트리(Heap Tree), 그중에서도 최소 힙(Min Heap)을 활용하면 효율적으로 해결할 수 있습니다. 먼저 모든 로프의 길이를 최소 힙에 삽입한 뒤, 가장 짧은 로프와 두 번째로 짧은 로프를 꺼내 연결합니다. 연결된 새 로프의 길이(두 길이의 합)는 다시 힙에 삽입합니다. 이 과정을 반복하여 힙에 요소가 하나만 남으면, 그때까지 누적된 비용이 곧 최소 연결 비용입니다.

입력 및 출력

입력:
로프의 길이: {4, 3, 2, 6, 5, 7, 12}
출력:
총 최소 비용: 103

알고리즘

findMinCost(array, n)

입력 − 로프 길이 리스트와 리스트에 담긴 원소의 개수

출력 − 로프를 모두 연결하기 위한 최소 비용

Begin
    minCost := 0
    배열의 원소들로 우선순위 큐를 채운다 (값이 작을수록 높은 우선순위)
    while 큐가 비어 있지 않으면, do
        item1 := 큐에서 가장 작은 값을 꺼내 삭제
        item2 := 큐에서 다음으로 작은 값을 꺼내 삭제
        minCost := minCost + item1 + item2
        (item1 + item2)를 큐에 다시 삽입
    done
    return minCost
End

예제 코드 (C++)

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

int findMinimumCost(int arr[], int n) {
    // 값이 작을수록 높은 우선순위를 갖도록 우선순위 큐 설정 (최소 힙)
    priority_queue< int, vector<int>, greater<int>>queue(arr, arr+n);

    int minCost = 0;

    while (queue.size() > 1) {          // 큐에 원소가 2개 이상 남아 있는 동안
        int item1 = queue.top();        // item1: 가장 짧은 로프
        queue.pop();

        int item2 = queue.top();        // item2: 두 번째로 짧은 로프
        queue.pop();

        minCost += item1 + item2;       // 두 로프를 연결하고 비용 누적
        queue.push(item1 + item2);      // 연결된 로프를 다시 큐에 삽입
    }
    return minCost;
}

int main() {
    int ropeLength[] = {4, 3, 2, 6, 5, 7, 12};
    int n = 7;
    cout << "Total minimum cost: " << findMinimumCost(ropeLength, n);
}

실행 결과

Total minimum cost: 103

동작 원리 살펴보기

왜 항상 가장 짧은 두 로프부터 연결해야 할까요? 한 번 연결된 로프는 이후 연결 과정에서 계속해서 비용에 더해지기 때문입니다. 즉, 길이가 짧은 로프일수록 여러 번 더해질 가능성이 높으므로, 짧은 로프를 먼저 합치면 전체 비용을 줄일 수 있습니다. 이는 허프만 코딩(Huffman Coding)의 아이디어와 동일한 원리입니다.

예시 입력 {4, 3, 2, 6, 5, 7, 12}의 경우, 2+3=5 → 4+5=9 → 5+6=11 → 7+9=16 → 11+12=23 → 16+23=39 순으로 연결되며, 총 비용은 5+9+11+16+23+39 = 103이 됩니다.

이 알고리즘의 시간 복잡도는 힙 연산 기준으로 O(n log n)이며, 공간 복잡도는 O(n)입니다.