백준 알고리즘 1715번: 카드 정렬하기

문제 정보

---

1715번: 카드 정렬하기

 

핵심

---

답이 도출되는 과정을 이해하면 문제를 쉽게 풀 수 있다!

간단히 설명하면, 이 문제는 카드 묶음 중에서 가장 작은 카드 묶음 두 개를 더해 가면서 문제를 풀이하면 된다

 

카드 묶음이 5장 있다고 가정해 보자, 우리는 카드 묶음 두 개를 고를 때 가지고 있는 묶음 중에서 가장 작은 2개의 묶음을 선택하면 된다

위처럼 모든 카드 묶음을 합쳐서 하나의 묶음으로 만들 때, (10, 20), (30, 30), (40, 50), (60, 90) 과 같이 합치면 최소의 경우가 되는 것이다

 

또한, 이렇게 합치는 과정 속에서 카드 묶음 중 가장 작은 두 묶음만 뽑으려고 할 때 효율적인 자료구조는 우선순위 큐 이다

우선순위 큐 혹은 Heap 을 만들고, 두 개의 묶음을 poll() 하면 가장 작은 묶음 두 개가 나올 것이다

 

보면 위 사진에서 초록 수들의 합이 정답이 된다는 것을 알 수 있다

따라서, 어딘가에 변수를 두고 여기에 더한 값을 계속해서 저장해 가면서 종료 조건(큐에 한 개의 수만 남았을 때)를 설정해 주면 된다

 

풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Queue<Integer> queue = new PriorityQueue();
        int N = Integer.parseInt(br.readLine());
        for(int i=0; i<N; i++) {
            int card = Integer.parseInt(br.readLine());
            queue.add(card);
        }
        int sum = 0;
        while(queue.size() > 1) {
            int A = queue.poll();
            int B = queue.poll();

            sum += (A + B);
            queue.add(A+B);
        }
        System.out.println(sum);
    }
}

 

Source Code on GitHub

---