[BOJ] 1715번 카드 정렬하기

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1715

 

문제를 처음 접하고 예제 입력만을 가지고 단순히 생각해 보면 

숫자 카드 묶음을 1차원 배열로 만들고 이를 오름차순 정렬해서 앞에서부터 더해 나가면 되지 않을까 생각할 수 있지만

그건 오름차순으로 정렬하고 가장 작은 값들 2개를 골라 더한뒤 그다음 작은 값이 배열의 다음 값인 경우에만 가능하다

예를 들어 문제의 예제처럼 10, 20, 40 일 경우에는

(10 + 20) = 30 이고 해당 값 다음으로 큰 값이 40이기 때문에 단순 1차원 배열에서 오름차순 정렬로 풀 수 있다.

 

하지만 만약 주어진 카드 묶음이 10, 10, 10, 10, 10이라고 하면

오름 차순 정렬 후 가장 작은 2개의 값은 10, 10 이기때문에 둘을 합치면 20이 된다.

하지만 배열에는 아직 20보다 작은 10이 남아있다.

따라서 남은 배열에 가장 작은 2개의 값은 10, 10 으로 합치면 20 이 된다.

이런 식으로 매 순간마다 가장 작은 2개의 값을 합쳐나가는 그리디 문제라는 것을 알 수 있고,

가장 작은 값들을 2개 뽑아내기 위해서는 PriorityQueue를 사용하면 쉽게 해결할 수 있다.

 

package boj;

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

public class BOJ1715 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Long[] arr = new Long[N];

        for(int i = 0; i < N; i++){
            arr[i] = Long.parseLong(br.readLine());
        }

        PriorityQueue<Long> pq = new PriorityQueue<>();
        for(int i = 0; i < arr.length; i++){
            pq.add(arr[i]);
        }

        long answer = 0;

        while(pq.size() >= 2){
            long temp = pq.poll() + pq.poll();
            answer += temp;
            pq.add(temp);
        }

        System.out.println(answer);
    }
}