[BJ] 1715 카드 정렬하기 Java

백준 1715 카드 정렬하기 

문제

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

1715번: 카드 정렬하기

 

아이디어

• 문제의 예시에도 나와있듯이 최소한으로 비교하기 위해서는 가장 작은 값끼리 먼저 더해야한다
• 즉 10, 20, 40이면 (10+20) + (30+40) 을 해야함
• 계속해서 작은 값을 먼저 더해야되기 때문에 PriorityQueue 우선순위큐를 사용하면 된다

코드

package baekjoon;
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 num = sc.nextInt();
            pq.offer(num); // 우선순위큐 이기 때문에 poll()할때 작은 값이 먼저 나옴
        }

        int answer = 0;

        // 큐에 숫자가 두개 있어야 더 할 수 있음
        while (pq.size() > 1) {
            int a = pq.poll();
            int b = pq.poll();
            answer += a+b;
            pq.offer(answer); // 더한값을 다시 넣어줘야 최대 횟수 가능
            // 10+20 = 30 했다면, 30 + 40 해야되기 때문에 30넣어줌
        }
        System.out.println(answer);
    }
}