문제
행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.
입력
입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다.
다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다.
태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.
출력
- 티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.
제한
- 시간 제한 : 1초
- 메모리 제한 : 512MB
문제 풀이 과정
키가 정렬되서 입력된다. 또한 같은 조는 인접한 키여야 한다.
먼저 인접한 사람끼리의 차를 구하면 된다.
예시로 [1, 3, 5, 6, 10] 가 입력된다면 인접한 사람끼리의 차는 다음과 같다.
[3-1, 5-3, 6-5, 10 - 6] = [2, 2, 1, 4] 가 인접한 사람끼리의 차다.
K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 구해야 되고, 티셔츠를 만드는 비용은 키의 차이기 때문에 인접한 사람끼리의 차를 오름차순으로 정렬한다.
그럼 [1, 2, 2, 4] 가 된다.
K개의 조를 만들려면 K-1 번 찢어줘야 한다.
가장 큰 K-1 개를 제외하고 전부 더해주면 된다.
즉 정렬된 키차이 배열 크기인 N-1에서 K-1만큼을 제외한 N-1-(K-1) 만큼 뽑아내면 된다.
즉 N -K 까지 모두 더하면 된다.
정답 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
class Main13164 {
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());
st = new StringTokenizer(br.readLine());
int[] q = new int[N];
for (int i = 0; i < N; i++) {
q[i] = Integer.parseInt(st.nextToken());
}
int[] diff = new int[N - 1];
for (int i = 0; i < N - 1; i++) {
diff[i] = q[i + 1] - q[i];
}
Arrays.sort(diff);
int answer = 0;
for (int i = 0; i < N - K; i++) {
answer += diff[i];
}
System.out.println(answer);
}
}