백준 15903 - 카드 합체 놀이

Java

15903 번 - 카드 합체 놀이

문제

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

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

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

접근 방법

문제는 간단하였다.
점수를 가장 적게 만드는게 목표이므로, 가장 작은 수 2개만 더하여 갱신한다.
m번 만큼의 반복을 진행 할 때, Arrays.sort()를 통하여 오름차순으로 정렬한다.
인덱스 0과 1이 제일 작은 수이므로 그 두개를 더하여 그 자리에 갱신한다.
단, 초기에 각 값이 최대인 1,000,000이 될 수 있으므로, int형으로는 담지 못한다. 따라서 long으로 충분히 담을 크기의 공간을 준다.

코드

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

public class Main {
	static int n, m;
	// 타입을 long으로 선언한다.  
	static long sum, result;
	static long[] arr;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	n = stoi(stk.nextToken());
    	m = stoi(stk.nextToken());
    	arr = new long[n];
    	stk = new StringTokenizer(br.readLine());
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}
		// 정렬을 하여 제일 작은 2개의 수의 합을 구하고 갱신한다.  
    	for(int i = 0; i < m; i++) {
    		Arrays.sort(arr);
    		sum = arr[0] + arr[1];
    		arr[0] = sum;
    		arr[1] = sum;    		
    	}
    	for(long v : arr) {
    		result += v;
    	}
    	System.out.println(result);
    	br.close();
	}

	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

⭐★★★★

후기

long 타입의 함정이 있었지만, 예전에 배운 것을 잊지 않고 통과하였다.

개선할 점

없