[백준] S2 14241번 슬라임 합치기

문제 출처 - Baekjoon Online Judge

문제는 여기

14241번: 슬라임 합치기

[문제] 

영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.

모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.

영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오.

[입력]

첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.

둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다.

[출력]

첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다.

 

 

---

[풀이]

1. 입력받은 슬라임 크기들을 정렬해준다.

2. Arrays.sort를 사용해 정렬을 해주면 오름차순으로 정렬이 되는데, 내림차순으로 정렬된 것을 사용해야하므로 뒤에서부터 사용한다.

3. 뒤에서 부터 합치며 i와 i+1의 슬라임이 합쳐진 크기를 i에 저장시켜 준다.

4. 합쳐지면서 발생하는 점수를 계속 추가해준다.

[접근]

1. 큰 순서대로 슬라임을 합치면서 점수를 구하면 최고 점수를 구할 수 있다는 것을 확인하고 이 방식으로 문제를 해결하였다.

[코드]

package BOJ_silver;

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

public class Main_S2_14241 {
	static int n;
	static int[] arr;
	static int score;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n];
		
		// 입력받기
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		// 정렬
		Arrays.sort(arr);
		
		// 뒤에서부터 사용
		for (int i = n - 2; i >= 0; i--) {
			// 점수를 더해준다.
			score += arr[i] * arr[i + 1];
			// 커진 슬라임의 크기를 저장해준다.
			arr[i] = arr[i] + arr[i + 1];
		}
		
		// 점수를 출력한다.
		System.out.println(score);
	}
}