[백준 / 골드4] 1715 카드 정렬하기 (Java)

문제 보기

사용한 것

• 작은 카드 뭉치부터 뽑기 위한 우선순위 큐

풀이 방법

• 우선순위 큐를 사용해서 가장 작은 두 카드 뭉치를 뽑는다.
• 카드 뭉치의 합을 answer에 더한다.
• 두 카드 뭉치를 합쳐 pq에 다시 넣는다.
• pq에 하나가 남을 때까지 반복한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            pq.offer(Integer.parseInt(br.readLine()));
        }

        // 가장 작은 두 수 합쳐서 PQ에 다시 넣기
        int answer = 0;
        while (pq.size() > 1) {
            int num1 = pq.poll();
            int num2 = pq.poll();
            int sum = num1 + num2;
            answer += sum;
            pq.offer(sum);
        }

        System.out.println(answer);
    }
}