백준 1715 카드 정렬하기(JAVA)

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

1715번: 카드 정렬하기

 

 

풀이)

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

public class Main_BJ_1715_카드정렬하기 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i=0; i<n; i++){
            pq.offer(Integer.parseInt(br.readLine()));
        }
        int max = 0;
        while(pq.size()>1){
            int a = pq.poll();
            int b = pq.poll();
            pq.offer(a+b);
            max += a+b;
        }
        System.out.println(max);

    }//main
}

해당 문제는 greedy로 해결할 수 있다.

 

1. 카드를 priority queue에 넣어두고 차례로 뽑는다.(자동으로 오름차순 정렬!)

2. 그 후 priority queue에서 두 개씩 뽑으며 수를 더하고, 다시 priority queue에 넣어둔다.(누적합이기 때문)

3. 이때, 뽑은 두 수를 더한 값을 계속 누적해서 더해줄 변수에 넣어둔다.

4. 이 수를 출력하면 끝!

 

사실 본격적으로 풀기 전에 어쩌다보니 푸는걸 얼핏 들은적이 있어서... 금방 풀었디만...

혼자 아이디어를 생각했을땐 조금 헷갈렸을 것 같기도 하다.

 

다른 골드 문제도 정복해 봐야징!