OJ
[BOJ] 13164 행복 유치원 (JAVA)
P3PP4
2023. 6. 7. 10:00
https://www.acmicpc.net/problem/13164
13164번: 행복 유치원
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로
www.acmicpc.net
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
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));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
if (N == K) {
System.out.print(0);
return;
}
int[] input = new int[N];
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
input[i] = Integer.parseInt(st.nextToken());
} // end of input
for (int i = 1; i < N; i++) {
pq.offer(input[i] - input[i - 1]);
}
int sum = input[N - 1] - input[0];
for (int i = 1; i < K; i++) {
sum -= pq.poll();
}
System.out.print(sum);
}
}