[백준 11047] 카드 정렬하기 (그리디)

그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

 

그리디 알고리즘의 핵심 이론

1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다.
2. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1. 로돌아가 같은 과정을 반복한다.

문제

 

풀이

먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미친다. 따라서 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다. 즉, 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 ㅃㅂ고 다시 데이터에 넣고 정렬해야한다. 이 문제는 우선순위 큐를 이용하면 편하다.

 

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    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 data = sc.nextInt();
            pq.add(data);
        }

        int data1 = 0;
        int data2 = 0;
        int sum = 0;

        while (pq.size() != 1) {
            data1 = pq.remove();
            data2 = pq.remove();
            sum += data1 + data2;
            pq.add(data1 + data2);
        }
        System.out.print(sum);
    }
}