카드 합체 놀이

문제

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

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

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

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

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

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입력 1

3 1
3 2 6

예제 출력 1

16

예제 입력 2

4 2
4 2 3 1

예제 출력 2

19

문제 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ15903 {
    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());

        PriorityQueue<Long> cards=new PriorityQueue<>();

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

        for(int i=0;i<m;i++){
            long a=cards.poll();
            long b=cards.poll();
            cards.add(a+b);
            cards.add(a+b);
        }

        long sum=0;
        while(!cards.isEmpty()){
            sum+=cards.poll();
        }

        System.out.println(sum);
    }
}

카드를 두 개씩 뽑아 합을 구하고 두 카드의 합을 뽑았던 두 카드 대신 넣어주는 문제이다.

최종적으로 만들어진 카드에 적힌 수들의 합의 최소값을 구하는 것이므로 작은 값들만 합치다 보면 원하는 값을 얻을 수 있다.

즉, 갱신되는 카드의 값들 중 가장 작은 값 2개를 뽑아 더하고, 카드를 갱신하는 과정을 m번 반복하는 것이다.

배열을 만들고 두 카드의 합을 넣어줄때마다 sort해주는 방법도 있겠지만 ProrityQueue를 이용하면 조금 더 쉽게 만들 수 있다.

PriorityQueue 이용하여 값 넣어주기

PriorityQueue<Long> cards=new PriorityQueue<>();

for(int i=0;i<m;i++){
    long a=cards.poll();
    long b=cards.poll();
    cards.add(a+b);
    cards.add(a+b);
}

PriorityQueue 객체를 이용하여 우선순위큐 cards를 선언한다.

m번의 반복동안 제일 앞의 값, 즉 제일 작은 값을 두 개 뽑아 두 값의 합을 두 번 다시 넣어준다.

이렇게하면 따로 sort를 해주지 않아도 PriorityQueue의 특성으로 가장 작은 값이 앞으로 오도록 정렬된다.

이 과정을 m번 반복하고 모든 카드의 값들을 합하여 답을 출력하면 된다.

long sum=0;
while(!cards.isEmpty()){
    sum+=cards.poll();
}

주의할 점

이 문제에서 주의해야할 점은 카드의 값이 1,000,000까지 나올 수 있기 때문에 모든 카드의 값을 더했을 때 int로 표현할 수 있는 숫자의 범위를 넘어가는 경우가 나올 수 있다.

때문에 자료형을 int 대신 long을 사용하여 범위를 늘려준다.

---

처음에는 두 카드의 합을 카드 대신 넣어주는 건지 원래 카드의 값에서 추가해줘야하는지 판단하지 못해 시간이 걸렸고

문제를 파악한 후에는 int 자료형을 이용하여 코드를 구현했으나 정답이 되지 않아서 자료형의 범위를 늘려주어야한다는 글을 보고 long으로 바꿔 제출하니 정답 처리가 되었다.