[백준] 14241 - 슬라임 합치기

[문제링크]

14241번: 슬라임 합치기

 

0. x와 y 슬라임으로, x+y 슬라임을 만들며, x*y 점수를 획득한다

 

1. N번째 합칠 슬라임의 무게가 y였다면, N+1, N+2...번째 연산에도 y가 포함되게 된다

 

2. 크기가 큰 슬라임을 빠르게 합쳐, 이후 연산들에 최대한 많이 포함되도록 해야 한다 (그리디)

 

3. 슬라임을 크기순으로 2개씩 꺼내며 합쳐나간다.

 

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

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		PriorityQueue<Integer>pq = new PriorityQueue<>();
		
		int N = pint(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		for (int i = 0; i < N; i++) {
			pq.offer(pint(st.nextToken()));
		}
		
		int score = 0;
		while(pq.size()!=1) {
			int fst = pq.poll();
			int snd = pq.poll();
			score+=fst*snd;
			pq.offer(fst+snd);
			
		}
		
		System.out.println(score);
		
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면