[백준] 13164번: 행복 유치원 - 자바

🔈 문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.
이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

 

📝입력

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

 

📑출력

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

 

📚 문제 풀이

 

k개로 쪼갰을 때 한 묶음 중 최소값과 최대값의 차이를 최소로 만드는 문제였다.

배열을 만들어서 정렬된 원생들의 이웃한 원생의 키차이를 담는다. 총 n명의 원생이 있으니 배열의 크기는 n-1이 된다.

(2번-1번, 3번-2번, 4번-3번 라잌딗)

그리고 이 차이를 담은 배열을 내림차순으로 정렬한다. 그 다음 그 배열의 k번째부터 n-1까지 더한 값이 구하고자 하는 값이다.

 

쉽게 생각하면 특출나게 큰 원생이나, 특출나게 작은 원생은 팀으로 묶지 않고 그냥 혼자 냅두는 것이다. 만약 이 친구들이 팀에 들어간다면 차이를 크게 만들것이기 때문이다. 그렇기 때문에 그리디 적으로 작은 차이를 갖는 애들을 묶어 설레는 키차이를 최소화 한것이다.

 

💻 코드

import java.io.*;
import java.util.*;
 
public class Cos{
    public static void main(String[] args)throws Exception{
        // Fast input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer s = new StringTokenizer(br.readLine().trim());
        int n = Integer.parseInt(s.nextToken());
        int k = Integer.parseInt(s.nextToken());
 
        int[] nums = new int[n];
        int res = 0;
        
        // for difference arrays
        Integer[] diff = new Integer[n-1];
        s = new StringTokenizer(br.readLine().trim());
        for (int i=0;i<n;i++){
            nums[i] = Integer.parseInt(s.nextToken());
        }
        for (int j=0;j<n-1;j++){
            diff[j] = nums[j+1]-nums[j];
        }
        // sort
        Arrays.sort(diff, Collections.reverseOrder());
 
        for (int i=k-1;i<diff.length;i++){
            res += diff[i];
        }
        System.out.println(res);
    }
}

 

🍭 시행착오

파이썬과 자바

사실 이 문제는 파이썬으로 먼저 풀었고, 그 뒤 자바로도 소스코드를 짜보았다.

1784ms에서 960ms로 단축된 이유는 빠른 입출력을 사용했기 때문이다.

 

🔗 문제링크 행복유치원

13164번: 행복 유치원