사용자 도구

사이트 도구


ps:problems:boj:13975

파일 합치기 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호13975
문제명파일 합치기 3
레벨골드 5
분류

그리디, 우선순위큐

시간복잡도O(nlogn)
인풋사이즈n <= 1,000,000
사용한 언어Python
제출기록150904KB / 5832ms
최고기록5076ms
해결날짜2021/03/09

풀이

  • 파일 합치기 1, 2, 4는 동일한 문제를 n의 범위만 다르게 한 것이지만, 이 문제는 문제 자체가 살짝 다르다. 다른 파일 합치기들은 인접한 파일들만 합칠 수 있어서 결국 최적 이진 검색 트리문제와 동일한 문제가 되지만, 이 문제에서는 인접하지 않은 파일들끼리도 합칠 수 있다.
  • 인접하지 않은 파일들끼리도 합칠수 있다면, 그리디한 방식으로 해결 가능한다. 매 단계에서 가장 크기가 작은 파일 두개를 골라서 합치는 것을 반복하면 된다. huffman coding을 만드는 것과도 동일한 문제이다.
  • 크기가 작은 파일 두개를 골라서 합치는 것은, 우선 순위 큐를 이용해서 빠르게 처리가능하다. extract_min을 두번 하고, 더한 값을 insert하면 O(logn)에 처리할 수 있고, 이것을 n-1번 해야 하므로 총 시간 복잡도는 O(nlogn).

코드

"""Solution code for "BOJ 13975. 파일 합치기 3".

- Problem link: https://www.acmicpc.net/problem/13975
- Solution link: http://www.teferi.net/ps/problems/boj/13975
"""

import heapq


def main():
    T = int(input())
    for _ in range(T):
        K = int(input())  # pylint: disable=unused-variable
        file_sizes = [int(x) for x in input().split()]

        cost = 0
        heapq.heapify(file_sizes)
        while True:
            try:
                f1 = heapq.heappop(file_sizes)
                f2 = heapq.heappop(file_sizes)
                cost += f1 + f2
                heapq.heappush(file_sizes, f1 + f2)
            except IndexError:
                break

        print(cost)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
S Q Q​ X W
 
ps/problems/boj/13975.txt · 마지막으로 수정됨: 2021/03/09 10:38 저자 teferi