백준 온라인 저지(Baekjoon Online Judge) - 13975 : 파일 합치기 3

 

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

13975번: 파일 합치기 3

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int K;
        cin >> K;

        priority_queue<long long, vector<long long>, greater<long long>> pq;  // 우선순위 큐 (최소 힙)
        for (int i = 0; i < K; i++) {
            int size;
            cin >> size;
            pq.push(size);
        }

        long long totalCost = 0;

        while (pq.size() > 1) {
            long long file1 = pq.top();
            pq.pop();
            long long file2 = pq.top();
            pq.pop();

            long long mergeCost = file1 + file2;
            totalCost += mergeCost;

            pq.push(mergeCost);
        }

        cout << totalCost << endl;
    }

    return 0;
}

 

이 코드는 파일 병합 비용을 계산하는 프로그램을 구현한 것입니다. 주어진 입력에 따라 여러 개의 파일을 병합하며, 각 파일의 크기에 따른 비용을 계산하여 최소 비용을 출력합니다.

주요 부분을 살펴보겠습니다:

1. #include <iostream>: C++의 표준 입력 및 출력을 사용하기 위한 라이브러리입니다.

2. #include <queue>: 우선순위 큐를 사용하기 위한 라이브러리입니다.

3. using namespace std;: 표준 라이브러리를 사용하기 위해 std 네임스페이스를 사용합니다.

4. int main(): C++ 프로그램의 진입점입니다.

5. int T; cin >> T;: 테스트 케이스의 개수를 입력받습니다.

6. while (T--) { ... }: 입력받은 테스트 케이스 개수만큼 반복합니다.

7. int K; cin >> K;: 현재 테스트 케이스에서 병합할 파일의 개수를 입력받습니다.

8. priority_queue<long long, vector<long long>, greater<long long>> pq;: 우선순위 큐를 선언합니다. 이 우선순위 큐는 최소 힙으로 구현되어 있어 작은 값부터 우선적으로 접근할 수 있습니다.

9. for (int i = 0; i < K; i++) { ... }: 현재 테스트 케이스에서 파일의 크기를 입력받아 우선순위 큐에 저장합니다.

10. long long totalCost = 0;: 총 병합 비용을 나타내는 변수를 초기화합니다.

11. while (pq.size() > 1) { ... }: 우선순위 큐에 남은 파일이 하나 이상일 때까지 반복합니다.

12. long long file1 = pq.top(); pq.pop();: 우선순위 큐에서 가장 작은 파일을 가져옵니다.

13. long long file2 = pq.top(); pq.pop();: 우선순위 큐에서 두 번째로 작은 파일을 가져옵니다.

14. long long mergeCost = file1 + file2;: 두 파일을 병합한 비용을 계산합니다.

15. totalCost += mergeCost;: 총 병합 비용에 현재 병합 비용을 더합니다.

16. pq.push(mergeCost);: 병합한 파일의 크기를 우선순위 큐에 다시 저장합니다.

17. cout << totalCost << endl;: 현재 테스트 케이스의 총 병합 비용을 출력합니다.

18. return 0;: 프로그램을 종료합니다.

이 코드는 우선순위 큐를 사용하여 파일 병합 작업을 수행하는 방식으로 최소 비용을 구하는 그리디 알고리즘을 구현하였습니다.

우선, 입력으로 주어진 테스트 케이스의 개수를 T 변수에 저장하고, while 반복문을 통해 각 테스트 케이스를 처리합니다. 각 테스트 케이스에서는 병합할 파일의 개수를 입력받고, 파일의 크기를 우선순위 큐에 저장합니다.

우선순위 큐를 사용하면 가장 작은 값이 우선적으로 접근되기 때문에, 파일 크기가 작은 파일들을 먼저 병합하면서 최소 비용을 구할 수 있습니다.

while 반복문에서는 우선순위 큐에 파일이 두 개 이상 남아있는 경우에 계속해서 병합 작업을 수행합니다. 가장 작은 파일(file1)과 두 번째로 작은 파일(file2)을 가져와 병합 비용을 계산하고, 이를 총 병합 비용인 totalCost에 더합니다. 그리고 병합한 파일의 크기를 우선순위 큐에 다시 저장합니다. 이 과정을 반복하여 최종적으로 우선순위 큐에는 하나의 파일 크기만 남게 됩니다.

마지막으로, 각 테스트 케이스의 총 병합 비용인 totalCost를 출력하고 프로그램을 종료합니다.

이 알고리즘은 그리디 접근 방식으로 항상 현재 단계에서 가장 작은 비용을 선택하여 병합하므로, 최소 비용을 구할 수 있는 효율적인 방법입니다. 복잡도는 주어진 파일의 개수에 따라 결정되며, 파일의 개수를 K라고 할 때, 우선순위 큐에 파일 크기를 삽입하는 시간은 O(KlogK)이고, 병합 작업은 파일이 하나만 남을 때까지 최대 K-1번 수행되므로 O(KlogK)입니다. 따라서 총 시간 복잡도는 O(KlogK)입니다.

이 코드는 파일 병합 비용을 최소화하는 그리디 알고리즘의 구현 예시로 사용될 수 있습니다.

 

* 해당 게시물은 ChatGPT를 참고하여 작성되었음을 알립니다.