[BJ] 1715 카드 정렬하기

백준 1715 카드 정렬하기

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

1715번: 카드 정렬하기

아이디어

• 카드를 최소한의 비교로 합치기 위해서는 매번 묶음의 개수가 가장 적은 것들을 더해주면 된다
• 우선순위큐를 사용하여 매번 가장 낮은 숫자들을 더하면 결과를 확인할 수 있다

코드

import java.util.*;

class BJ1715 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int i=0; i<n; i++) {
            int val = sc.nextInt();
            pq.offer(val);
        }
        
        int data1 = 0;
        int data2 = 0;
        int sum = 0;
        
        // 큐에 1개가 남았다는 것은 더할숫자가 더 이상 없음
        while (pq.size() != 1) {
            data1 = pq.poll();
            data2 = pq.poll();
            sum += data1 + data2; // 누적 합에 더하고
            pq.add(data1 + data2); // 2개의 값을 더한 값은 다시 큐에 넣어줘야함
        }

        System.out.println(sum);
    }
}