[알고리즘 / 백준] 1715 - 카드 정렬하기

www.acmicpc.net/problem/1715

1715번: 카드 정렬하기

 

문제는 위와 같으며 크기가 가장 작은 카드 묶음들을 먼저 합쳤을 때, 비교 횟수가 가장 적다는 점을 이용하여 문제를 해결할 수 있습니다.

 

파이썬 코드는 다음과 같습니다.

from sys import stdin
import heapq

heap = []
n = int(stdin.readline())
for _ in range(n):
    bundle = int(stdin.readline())
    heapq.heappush(heap, bundle)  # 모든 카드 묶음 수를 heap 에 저장

result = 0

while len(heap) > 1:
	# 최소 카드 묶음 2개를 찾아 먼저 합치고 그 결과 다시 힙에 저장
    min1 = heapq.heappop(heap)
    min2 = heapq.heappop(heap)
    result += min1 + min2
    heapq.heappush(heap, min1 + min2)

print(result)

 

자바 코드는 다음과 같습니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int result = 0;
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            heap.add(num);
        }

        while (heap.size() > 1) {
            int min = heap.poll() + heap.poll();
            result += min;
            heap.add(min);
        }

        System.out.println(result);
    }
}