[백준] S2 15903번 카드 합체 놀이(JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

15903번: 카드 합체 놀이

[문제] 

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

아기 석환이는 자연수가 쓰여진 카드를 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. 2장의 카드를 골라 합치고 이전에 선택된 2장의 카드를 합으로 변경한다.

2. 주어진 횟수만큼 1번을 반복한다.

3. 반복을 끝내고 모든 합을 구한다.

4. 구해진 합의 최솟값을 구한다.

[접근]

1. 2장의 카드를 골라서 합으로 변경을 해주기를 반복할 때, 변경이 될 때 가장 작은 값이 돼야 모든 합이 최솟값이 된다.

2. 2장의 카드를 주어진 카드 중 가장 작은 2개의 카드로 선택을 하여 해당 카드를 합으로 변경해준다.

3. 우선순위 큐를 사용해서 입력된 값들을 자동으로 정렬해주고 가장 작은 값을 출력하도록 하였다.

4. m만큼 반복한 후 합을 구해준다.

[코드]

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

public class Main {
	static long n;
	static long m;
	static long result;
	static PriorityQueue<Long> queue;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
        // 값 입력받기
		n = Long.parseLong(st.nextToken());
		m = Long.parseLong(st.nextToken());
		
        // 우선순위 큐 생성
        queue = new PriorityQueue<Long>();

		// 카드 입력받기
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
        	queue.offer(Long.parseLong(st.nextToken()));
        }
        
        // 우선순위에서 가장 작은 카드 2개를 뽑아주기
        for (int i = 0; i < m; i++) {
        	long a = queue.poll();
        	long b = queue.poll();
        	long sum = a + b; // 뽑은 카드를 합해주기
        	
        	queue.offer(sum); // 합을 큐에 2번 넣어준다.
        	queue.offer(sum); // a와 b를 합으로 변경하는 것이기 때문
        }
        
        // 큐에 든 값들을 빼서 다 더해준다.
        for (int i = 0; i < n; i++) {
        	result += queue.poll();
        }
        
        // 합을 출력한다.
        System.out.println(result);
	}
}