[JAVA] 백준 1715 카드 정렬하기

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

 

문제분석

카드를 최소한으로 비교하는 상황을 찾고, 그때 비교 횟수를 출력하는 문제이다. 예를들어, 10,20,40이 있으면 10과 20을 먼저 합치고, 만들어진 30과 40을 합치면 된다. 그리디 알고리즘 연습으로 선택한 문제인데, 우선순위 큐 까지 배울 수 있는 좋은 문제인 것 같다. 그리디인 만큼 '최소해' 를 먼저 찾아야 한다.

해결과정

첫 번째로 생각한 부분 최적해는, 정렬 이후 '작은 카드 더미부터 합쳐나가기' 였다. 하지만 틀렸고, 이유를 생각해보니 더 좋은 방법이 존재했다. 

 

10, 20, 20, 20, 100으로 이루어진 상황이다. 첫번째 아이디어로 접근하면 정답이 나오지 않는다->부분 최적해가 아님.

두번째 상황이 최적해 인 것을 보고, 두번째 상황을 잘 살펴보니, 각 단계별로 '가장 작은 두 더미 카드를 섞음' 이였다. 연역적으로 떠올린 것은 아니긴 하나...

여튼,

1. 우리의 목적은 '카드 더미를 하나로 합치는 것'

2. 각 단계는 단순히 '카드 더미를 합치는 행위'

3. 한 단계를 거칠 때 마다 카드 더미는 1개씩 줄어든다.

4. 카드 더미가 1개가 될 때까지, 무조건 단계를 반복한다.

이다.

따라서, 가장 작은 값 2개만 선택해서 더하면 되는, 아주 아주 단순한 문제였다.

이를 구현하기 위해 list와 arr를 짬뽕하여 sort를 계속 진행하려고 했으나, 이를 반복한다면 시간 복잡도 측면에서 문제가 생길 것이라 예상했다(실제로, sort는 O(nlog n)인데 반해, priority queue의 add는 O(log n)이였다).

 

따라서 가장 좋은 선택지인 priority queue 자료구조를 사용하기로 하였고, 문제를 해결할 수 있었다(지금보니 N==2 를 따로 뺄 필요가 없는것 같다).

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i<N ; i++){
            pq.add(Integer.parseInt(br.readLine()));
        }
        if(N==1){
            bw.write(String.valueOf(0));
        }else if(N==2){
            bw.write(String.valueOf(pq.poll()+pq.poll()));
        }else{
            int result = 0;
            while(!pq.isEmpty()){
                int first = pq.poll();
                int second = pq.poll();
                result += first+second;
                if(!pq.isEmpty()){
                    pq.add(first+second);
                }
            }

            bw.write(String.valueOf(result));
        }
        bw.newLine();
        bw.flush();
        bw.close();
        

    }
}