[백준 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

 

문제 분석

정렬을 사용하고, 데이터에서 최소 / 최대를 뽑는 문제라는 점에서 그리디 알고리즘이라고 생각했습니다.

보통 문제를 이해할때 주어진 예제를 대입해보는 편입니다. 이번 문제의 경우 예제가 하나밖에 없음이 참 아쉬웠습니다.

출제자도 그런점을 알았는지 친절한 힌트를 제공해 주었습니다.

 

힌트를 바탕으로 나름 이해를 해보자면, for문을 돌면서 인접한 두 수의 차이를 cost에 더하면 됩니다. 

 

자세한 내용은 그림을 통해 설명 후 코드로 구현해보겠습니다.

이번 문제는 한 번만에 통과해 아주 기분이 좋습니다^^

 

 

코드 구현

import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		// 입력
		int n = kb.nextInt();
		int k = kb.nextInt();
		// n명의 학생을 넣는 배열 A
		int[] A = new int[n];
		for(int i=0; i<A.length; i++) {
			A[i] = kb.nextInt();
		}
		// A배열에서 인접한 학생의 차이를 넣는 배열 B
		int[] B = new int[n-1];
		for(int i=0; i<B.length; i++) {
			B[i] = A[i+1] - A[i];
		}
        	// 오름차순
		Arrays.sort(B);
		// 출력 : 최소비용 cost
		int cost = 0;
		
		for(int i=0; i<B.length-(k-1);i++) {
			cost += B[i];
		}
		System.out.println(cost);
	}
}