문제

아이디어

문제를 읽어봤을 때, 가장 크기가 큰 카드 묶음을 가장 마지막에 비교해야 한다는 것이 자명하다.

예를 들어, 1,000,000,000의 크기를 같는 카드 묶음이 있다고 가정해보자. 이 카드 묶음을 가장 처음 비교한다면, 계산 결과에 1,000,000,000은 두 번 이상 더해지게 될 것이고, 이는 바람직하지 못하다.
즉, 가장 큰 크기를 갖는 카드 묶음은 한 번만 더해지는게 바람직하며, 이를 위해서 항상 마지막에 비교해야 한다는 것을 확인할 수 있다.

그렇다면 큰 크기를 갖는 카드 묶음을 제외한다면 어떻게 해야 할까? 당연히 남은 카드 묶음 중 가장 큰 크기를 갖는 카드 묶음, 즉 전체 카드 묶음 중 두번째로 큰 카드 묶음을 마지막에 비교해야 할 것이다.

그렇다면 두번째 큰 카드 묶음도 제외한다면, 더 나아가서 N-2번째로 큰 카드묶음까지 차례로 제외한다면 남는 두 카드 묶음이 가장 처음 비교해야할 카드 묶음이다.
즉, 임의의 시점에서 가장 작은 크기를 갖는 두 카드 묶음을 비교할 때 최소 비교 횟수를 구할 수 있다.

이를 위해 우선순위 큐를 이용해 크기가 가장 작은 두 카드 묶음을 구해주고, 비교가 완료된 카드 묶음을 다시 우선순위 큐에 삽입한다. 이를 큐의 크기가 1이 될 때까지 반복해주면 될 것이다.

소스코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        int ans = 0;
        int N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {
            pq.add(Integer.parseInt(br.readLine()));
        }

        int next;
        while (pq.size() != 1) {
            next = pq.poll() + pq.poll();
            pq.add(next);
            ans += next;
        }

        System.out.println(ans);
    }
}

채점결과

사실 그리디로 풀어지겠지 싶어서 생각없이 풀었는데 우연히 맞았다.
요즘 바빠서 문제풀이 업로드를 못했는데 다시 시작해보자!