[BOJ/JAVA] 15903 카드합체 놀이

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

15903번: 카드 합체 놀이

합쳐진 카드 뭉치 중 작은것 2개의 합을 계속 더해나가는 문제

작은것 2개의 합을 다시 카드목록에 추가하므로 우선순위 큐를 이용했다.

 

사용 알고리즘 : 우선순위 큐, 그리디 알고리즘

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

public class java_15903 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 카드의 개수
        int n = Integer.parseInt(st.nextToken());
        // 카드 합체를 몇 번 하는지
        int m = Integer.parseInt(st.nextToken());

        // 카드 입력받기
        PriorityQueue<Long> cardList = new PriorityQueue<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cardList.add(Long.parseLong(st.nextToken()));
        }

        // 카드 합치기
        for (int i = 0; i < m; i++) {
            long first = cardList.poll();
            long second = cardList.poll();
            long result = first + second;
            cardList.add(result);
            cardList.add(result);
        }

        // 점수 계산하기
        long result = 0;
        while (!cardList.isEmpty()) {
            result += cardList.poll();
        }

        bw.write(result + "\n");

        br.close();
        bw.close();
    }
}