이것저것 개발 블로그

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

풀이)

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

public class Main_BJ_15903_카드합체놀이 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        PriorityQueue<Long> pq = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++)
            pq.offer(Long.parseLong(st.nextToken()));

        int cnt = 0;
        while(cnt < m){
            long a = pq.poll();
            long b = pq.poll();
            pq.offer(a+b);
            pq.offer(a+b);

            cnt++;
        }

        long sum = 0;
        int size = pq.size();
        for(int i=0; i<size; i++)
            sum += pq.poll();
        System.out.println(sum);

    }//main
}

해당 문제는 그리디로 푸는 문제로, priority queue를 사용하면 쉽게 풀 수 있다!

카드에서 작은 순서대로 정렬을 한 후, 앞에서 2개를 뽑아 더한 수를 다시 pq에 넣어두면, 다시 정렬이 된다.

이 과정을 m번 반복하면 끝!