[백준] 파일 합치기 3

문자열 합치기
파일 합치기 3

생각흐름

1. 파일 합치기 문제와 굉장히 비슷하다. 이것은 다이나믹 프로그래밍(메모이제이션)을 이용해 3중 for문으로 풀었다. 풀이
2. 하지만 책에선 그리디 알고리즘 항목에 있었다. 따라서 이것을 메모이제이션이 아닌 그리디한 방법으로도 풀 수 있을 것 같다.
3. 내가 다이나믹 프로그래밍을 잘 몰랐을 때 파일 합치기 문제를 그리디로 풀려고 했었다.
   1. 왜냐하면, 파일을 합친다는 것은 두 파일이 파일 합치는 과정에 참여한다는 것이다.
   2. 크기가 큰 파일이 참여를 덜한다면 결국 최소 비용이 나오기 때문이다.
4. 하지만 이것은 단순 정렬로는 구현할 수 없었다. 내가 간과했던 것은, 합쳐진 파일보다 다른 새 파일의 크기가 클 수도 있다는 사실이다.
5. 합쳐진 파일의 크기가 더 작으므로 이것이 우선적으로 파일을 합치는 데 참여해야 하는데, 그저 정렬한 채로 앞에서부터 합쳤으므로 이게 될 리가 없다.
6. 그래서 우선순위 큐를 사용했어야 했다. 합쳐진 파일도 새로 큐에 들어가 매번 크기가 가장 작은 파일 둘을 합칠 수 있는 것이다.

코드

import sys
import heapq


scan = sys.stdin.readline
printf = sys.stdout.write


def solution():
    T = int(scan())
    for t in range(T):
        tc()


def tc():
    K = int(scan())
    chapter_lengths = list(map(int, scan().split()))
    heapq.heapify(chapter_lengths)

    total_cost = 0
    while len(chapter_lengths) > 1:
        chapterA = chapter_lengths[0]; heapq.heappop(chapter_lengths)
        chapterB = chapter_lengths[0]; heapq.heappop(chapter_lengths)
        cost = chapterA + chapterB
        heapq.heappush(chapter_lengths, cost)
        total_cost += cost

    printf("%d\n" % total_cost)


solution()

문자열 합치기에 제출한 코드이다.

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;
typedef priority_queue<int, vector<int>, greater<int>> intQ;

void tc();

int main() {
    int C;
    scanf(" %d\n", &C);
    for (int i = 0; i < C; i++) {
        tc();
    }
    return 0;
}

void getInput(int &n, vector<int> &lengths) {
    scanf(" %d", &n);
    for (int i = 0; i < n; ++i) {
        int len;
        scanf(" %d", &len);
        lengths.push_back(len);
    }
}

void initQueue(intQ &pq, vector<int> &lengths) {
    for (auto len: lengths) {
        pq.push(len);
    }
}


void tc() {
    int n;
    vector<int> lengths;
    getInput(n, lengths);

    intQ pq;
    initQueue(pq, lengths);

    int totalCost = 0;
    while (pq.size() > 1) {
        int dest = pq.top(); pq.pop();
        int src = pq.top(); pq.pop();
        int cost = dest + src;
        pq.push(cost);
        totalCost += cost;
    }

    printf("%d\n", totalCost);
}

파일 합치기 3에 제출한 코드이다.