[백준 15903 JAVA] 카드 합체 놀이

 

그리디 알고리즘 문제

 

카드가 겹쳐지며 계속 사용되는 구조이다. 따라서 합이 최소가 되기 위해서는 작은 카드들이 최대한 많이 쓰여야한다.

priority queue에 넣어서 카드의 숫자가 작은 순서대로 카드를 합치면 최소치가 나온다.

 

단 덧셈의 횟수가 상당히 많으므로 자료형을 잘 고려해야한다.

 

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

public class Main {
    static PriorityQueue<Long> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long N = Integer.parseInt(st.nextToken());
        long M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            pq.add(Long.valueOf(st.nextToken()));
        }
        for (int i = 0; i < M; i++) {
            long a = pq.poll();
            long b = pq.poll();
            long temp = a + b;
            pq.add(temp);
            pq.add(temp);
        }
        long answer = 0;
        while (!pq.isEmpty()) {
            answer += pq.poll();
        }
        System.out.println(answer);
    }


}