백준 No.15903 카드 합체 놀이 - JAVA

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져 있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고  있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

 

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다.

2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어쓴다.

 

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다. 

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지는 알 수 없었다. 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자

 

 

입력

3 1
3 2 6

 

 

풀이

먼저 여기서 작은 점수를 계산하라고 했는데 해당 부분을 통해 오름차순 정렬해야 한다는 것을 알 수 있따. 그리고 값들을 결국 더한 다음 다시 오름차순 정렬이 되어야 그 다음 작은 수랑 더할 수 있다는 생각이 들어 바로 우선순위  큐를 사용해서 풀었다. 문제를 푸는 것까지는 문제가 없었는데 결과가 이상한 값이 나와서 찾아보니 마지막에 for문으로 queue.size만큼을 더하고 있었다.... queue는 빌때까지 while문을 돌리자...

그래서 queue에 제일 작은 값 두개 꺼내서 더하고 다시 그 값을 두번 넣어주면 된다. 이걸 M번 반복하고 queue를 모두 더해주면 정답이다.

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

public class Main {


    public static void main(String[] args) throws IOException {
        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());

        Long solution = 0L;

        PriorityQueue<Long> queue = new PriorityQueue<>();
        st = new StringTokenizer(br.readLine());

        for (int i = 0; i < N; i++) {
            queue.add(Long.parseLong(st.nextToken()));
        }

        for (int i = 0; i < M ; i++) {
            Long tempA = queue.poll();
            Long tempB = queue.poll();

            queue.add(tempA+tempB);
            queue.add(tempA+tempB);
        }

       while(!queue.isEmpty()){
           solution += queue.poll();
       }
        System.out.println(solution);

    }
}