[BOJ/백준] 15903 카드 합체 놀이 (S1)

문제

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

 

풀이

카드의 개수 n개에 대하여 합체를 m번 한다.

문제의 조건을 보면 두 장의 카드를 골라 카드에 쓰여진 수를 더하여 나온 수를 두 카드에 다시 덮어쓰는 것을 m번 반복하는 것이다.

그리고 합체가 다 끝났을 때, 남은 카드들의 합의 최소값을 계산하는 것이다.

 

예제 2번으로 다시 설명을 하자면 4장의 카드인 4, 2, 3, 1의 카드들을 2번 합체한다. 단, 남은 카드들의 합의 가장 잡은 값을 만들려면 매번 합체할 때마다 가장 작은 두 수를 뽑아서 더해야 한다. 그래서 우선순위 큐(PriorityQueue)의 기본형을 사용하여 poll() 할 때마다 가장 작은 수를 뽑도록 하였다.

1번째 합체 → 1, 2를 뽑아서 1+2=3을 두 카드에 덮어쓴다. → 4, 3, 3, 3

2번째 합체 → 3, 3을 뽑아서 3+3=6을 두 카드에 덮어쓴다. → 4, 6, 6, 3

합체가 끝나고 모든 카드의 합을 구하면 4+6+6+3 = 19가 나온다.

 

처음에 정수형 범위로 생각하고 풀어서 틀렸다. n(2 ≤ n ≤ 1,000), m(0 ≤ m ≤ 15×n) 이므로 n이 1000이고, m이 15x1000만큼 반복하면 값은 매우 커지며 대충 계산해도 int형은 넘어가기 때문에 long형을 사용해야 한다.

Code

import java.io.*;
import java.util.*;

public class Main {
    // Long 타입으로 해야됨
    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;
        long sum;
        long result = 0;
        long a, b;


        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());  // 카드 개수
        int m = Integer.parseInt(st.nextToken());  // 합체 횟수

        Queue<Long> queue = new PriorityQueue<>();  // 매 횟수마다 작은것 부터 뽑기 위해 우선순위 큐 사용

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

        for (int i = 0; i < m; i++) {  // 합체할 때마다 가장 작은 수 두 개를 뽑아서 더하고 다시 두 개를 넣는다.
            a = queue.poll();  // 빼고
            b = queue.poll();  // 빼고
            sum = a + b;  // 더하고
            queue.offer(sum);  // 다시 넣고
            queue.offer(sum);  // 다시 넣고
        }

        for (int i = 0; i < n; i++) {
            result += queue.poll();
        }

        bw.write(result + "");
        bw.flush();
        bw.close();
    }
}