문제 정의

문제

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다.

매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = 120 번의 비교가 필요하므로 덜 효율적인 방법이다.

N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000) 이어서 N개의 줄에 걸쳐 숫자 카드 묶음의 각각의 크기가 주어진다. 숫자 카드 묶음의 크기는 1,000보다 작거나 같은 양의 정수이다.

출력

첫째 줄에 최소 비교 횟수를 출력한다.

문제 풀이

문제 풀이 논리

• 비교 횟수가 점점 누적되어 더해지는 형태니까 적은 숫자 카드먼저 더하는게 유리하다!
• 처음에는 그래서 그냥 Array 로 정렬을 하고 앞에서부터 누적 덧셈을 해줬었다.. 근데 틀림!
  만약에 맨 처음 20 25 30 35 50 이렇게 카드가 있다고 치면 중간에 20+25 = 45로 뒤에 더해지는 값인 35보다 커져서 이 경우에 20+25한 다음 30+35하고 나서 20+25인 45를 더하는게 더 비교 횟수가 적어진다.
• 따라서, Priority Queue를 사용해서 그때그때 가장 작은 숫자 두개를 먼저 더하는 형식으로 코드를 다시 짰다.

큐에서 숫자 뽑기 알고리즘

        //큐에서 가장 작은 숫자부터 뽑아서 계산
        int temp_sum = 0;
        int result = 0;
        while (pq.size() > 1) {
            temp_sum = pq.poll() + pq.poll();
            result = result + temp_sum;
            pq.add(temp_sum);
        }
        System.out.println(result);

• queue에 숫자가 하나밖에 없으면 비교할 게 더이상 없는 거니까 while문을 멈추고, 숫자가 남아 있으면 계속 연산을 진행한다.
• temp_sum에 맨 앞 두 개 숫자, 그니까 가장 작은 숫자 두 개를 뽑아서 더한 값을 넣는다.
• result는 모든 비교 횟수가 누적된 값이어야 하므로 한 번 루프가 돌 때마다 temp_sum을 계속해서 더해준다.
• pq에 현재 더한 값인 temp_sum을 넣어 위 논리에 적은, 앞의 두 값을 더한게 뒤 값보다 커지는 경우를 방지하고 비교할 수 있게 한다.
• 마지막에 result를 프린트하면 끝!

전체 코드

package Greedy;

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

public class BOJ1715 {
    public static void main(String[] args) {
        //작은 숫자 뽑기 위해서 Integer형 priority queue 사용
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //초기화 및 입력 받아 배열 채우기
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        for (int i = 0; i < N; i++) {
            pq.add(s.nextInt());
        }

        //큐에서 가장 작은 숫자부터 뽑아서 계산
        int temp_sum = 0;
        int result = 0;
        while (pq.size() > 1) {
            temp_sum = pq.poll() + pq.poll();
            result = result + temp_sum;
            pq.add(temp_sum);
        }
        System.out.println(result);
    }
}