백준 1715번: 카드 정렬하기

문제 설명

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

접근법

• 가장 작은 숫자 두개를 합쳐야 합니다.
• 앞에 두개를 더했을때 정렬순서가 변할 수 있습니다. 그렇기 때문에 배열이나 리스트가 아닌 우선순위큐를 사용해야 합니다.

정답

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

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		for (int i = 0; i < N; i++) {
			pq.add(sc.nextInt());
		}
		int answer = 0;
		while (pq.size() >= 2) {
			int a = pq.poll();
			int b = pq.poll();
			answer += (a + b);
			pq.add(a + b);
		}
		System.out.println(answer);
	}

}