[JAVA] 백준 1715 그리디

 

 

 

 

1715번: 카드 정렬하기

문제

카드 묶음 2개가 주어졌을 때 이 두개의 묶음을 합쳐 정렬하기 위해서는 카드의 갯수를 더한 만큼 비교를해야 한다.

이 때 작은 묶음들부터 더해나가면서 비교하면 최소값이 된다.

카드 묶음들이 주어졌을 때 비교횟수가 가장 작은 최솟값을 구하시오.

풀이

우선순위 큐를 사용하여 큐에 들어오는 값들을 최솟값 순서대로 사용할 수 있도록 정렬해준다.

큐에서 값을 2개씩 꺼내어 값을 합하고 이 값을 큐에 다시 넣는다.

이 값의 합은 answer 더한다.

큐에 값이 1개가 남을 때까지 반복한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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> queue = new PriorityQueue<>();

        for(int i=0; i<N; i++){
            queue.add(Integer.parseInt(br.readLine()));
        }

        int answer = 0;
        while (queue.size() > 1){
            int x = queue.poll();
            int y = queue.poll();
            answer += x + y;
            queue.add(x + y);
        }

        System.out.println(answer);

    }
}

결과