알고리즘 문제 풀이/BOJ 실버
[백준] 14241 - 슬라임 합치기
natonato
2021. 7. 7. 09:36
14241번: 슬라임 합치기
영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다. 모든 슬라임은 양수 크기를 가지고 있다. 두
www.acmicpc.net
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);
}
}