[Java] 백준 13164번 : 행복 유치원

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

예제 입력 1

5 3
1 3 5 6 10

예제 출력 1

3

힌트

• 1조: 1, 3
• 2조: 5, 6
• 3조: 10

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	private static BufferedReader br;
	private static StringTokenizer st;
	
	private static int N, K;
	private static int []heights, diffs;
	
	public static void main(String[] args) throws IOException {
		br=new BufferedReader(new InputStreamReader(System.in));
		st=new StringTokenizer(br.readLine());
		N=Integer.parseInt(st.nextToken());
		K=Integer.parseInt(st.nextToken());
		
		heights=new int[N];	// 원생들의 키
		diffs=new int[N-1];	// 인접한 원생과의 키 차이
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<N;i++) heights[i]=Integer.parseInt(st.nextToken());
		for(int i=0;i<N-1;i++) diffs[i]=heights[i+1]-heights[i];
		Arrays.sort(diffs);	// 인접한 원생과의 키 차이 배열 오름차순 정렬
		
		int result=0;
		for(int i=0;i<diffs.length-(K-1);i++) result+=diffs[i];	// K개 조를 만들기 위해 (K-1)개의 연결을 자름
		System.out.println(result);
	}

}

1. 인접한 원생과의 키 차이를 배열에 저장합니다.

2. 인접한 원생과의 키 차이 배열을 오름차순 정렬합니다.

3. K개 조로 나누려면 인접한 (K-1)개의 연결을 끊어주면 됩니다. 따라서 키 차이가 큰 것부터 (K-1)개를 빼면 티셔츠를 만드는 최소 비용을 구할 수 있습니다.

4. 남은 차이의 합을 구합니다.