문제
백준 13164번 - 행복 유치원
아이디어
- 최소 비용이 되기 위해서는 최대한 키가 비슷한 원생끼리 조를 이루는 것이 유리하다.
- 입력으로 받는 원생들의 키를 순서대로 바로 뒤 원생의 키와 차이를 구한다.(원생들의 키는 정렬되어 입력됨)
- 키 차이 배열을 정렬한다.
- 이 정렬된 키 차이 배열의 앞에서부터
N - K
개를 골라서 합을 구하면 K
개의 조를 가장 최소 비용으로 티셔츠를 만들 수 있는 경우다.
- 키 차이 배열에서 값을 하나씩 더한다는 것은 원생을 2명씩 고르는 것과 같다.
예상 시간 복잡도
코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BJ_13164 {
public static void main(String[] args) throws IOException {
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());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int[] diff = new int[n - 1];
for (int i = 0; i < n - 1; i++) {
diff[i] = arr[i + 1] - arr[i];
}
Arrays.sort(diff);
int sum = 0;
for (int i = 0; i < n - k; i++) {
sum += diff[i];
}
System.out.println(sum);
}
}