BOJ 1715 - 카드 정렬하기(Java)

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

1715번: 카드 정렬하기

 

풀이

이전의 합이 누적되는 형태

    - (a + b) + (a + b + c) + (a + b + c + d) + ......

    - 각 합의 작은 값이 누적되는 횟수를 크게, 큰 값이 누적되는 횟수를 작게 해야함

 

불가능한 방법

입력 요소의 정렬 만으로는 해결 불가능 

    - ex) 60, 50, 70, 80

        - 요소 정렬 : 50, 60, 70, 80

        - 누적 합 -> (50 + 60) + (50 + 60 + 70) + (50 + 60 + 70 + 80) = 560

    - 남아있는 수인 70, 80보다 큰 (50 + 60)인 110이 누적되는 것은 비효율적

 

해결방법

계산마다 요소들 중 가장 작은 값이 누적되게 해야함, 계산 할 때마다 정렬이 필요-> 우선순위 큐

    - 모든 요소 우선순위 큐에 삽입 -> 50, 60, 70, 80

    - 우선순위 큐에 사이즈가 1이 될때까지 앞의 2개 요소를 더하고 큐에 삽입

        - 비교 횟수 += 더한 요소의 값    

while (!(pq.size() ==1)) {
    int a = pq.poll();
    int b = pq.poll();
    sum += (a + b);
    pq.add(a + b);
}

 

예시

                                - (50 + 60) + (70 + 80) + ( (50 + 60) + (70 + 80) )

                                    - 50, 60을 비교    -> 결과 값 = 110 

                                                                                    +

                                    - 70, 80을 비교    -> 결과 값 = 150

                                                                                    +

                                    - 110, 150을 비교 -> 결과 값 = 260

                                                                                    = 520

 

 

전체 코드

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

public class Main {

    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            pq.add(Integer.parseInt(st.nextToken()));
        }
        int sum = 0;

        // 초기 요소의 갯수가 1개라면 비교 횟수가 존재 X
        // 누적 합 과정 중 pq의 갯수가 한개가 남으면 비교가 끝남
        while ((pq.size() > 1)) {
            int a = pq.poll();
            int b = pq.poll();
            sum += (a + b);
            pq.add(a + b);
        }
        
        System.out.println(sum);
    }
}