백준 - 13614 행복 유치원(Java)

https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

 

그리디 문제입니다.

 

문제를 요약하면, 구간(조)를 나눠 구간에서 최대와 최소의 합이 가장 작게 만들어야 하는 문제입니다.

즉, 문제 풀이 순서는 다음과 같습니다.

1. 구간을 나눈다.
2. 최대와 최소의 차이를 구한다.

 

1. 구간을 나눈다.

최소로 차이를 만들기 위한 구간은 간격이 가장 큰 쪽부터 나누면 된다는 것입니다.

아래 그림으로 보겠습니다.

 

 

예제 입력과 같이 n 크기가 5이고, 키가 '1, 3, 5, 6, 10'이면 위 그림과 같이 나타납니다.

오름차순으로 입력 받았지만, 정렬되지 않았다면 정렬해야 합니다.

 

그리고, 우측 사람과의 키 차이를 저장합니다.

구간을 나눌 때에는 이 키 차이가 가장 큰 것부터 나누면 됩니다.

 

즉, 아래 그림과 같이 나누면 됩니다.

 

[3]과 [4]의 차이가 4로 최대이기 때문에 먼저 구분선을 설치합니다.

[0]과 [1]의 차이와 [1]과 [2]의 차이가 같지만, 앞선 [0]과 [1]의 사이에 구분선을 설치하면 됩니다.

 

[구현 코드]

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer stz = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(stz.nextToken());
        int k = Integer.parseInt(stz.nextToken());

        int[] tall = new int[n];
        stz = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            tall[i] = Integer.parseInt(stz.nextToken());
        }

        // 키순으로 정렬
        Arrays.sort(tall);

        // 키 간격의 차이와 그 위치를 저장함
        int[][] interval = new int[n-1][2];
        for (int i = 0; i < n-1; i++) {
            interval[i][0] = (tall[i+1] - tall[i]); // 키 차이
            interval[i][1] = i; // 위치
        }

        // 간격이 큰 순으로 정렬해서 구간을 나눔
        Arrays.sort(interval, (o1, o2) -> o2[0] - o1[0]);
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<k-1; i++){
            set.add(interval[i][1]);
        }

        // 다시 키순으로 오름차순 정렬
        Arrays.sort(interval, (o1, o2) -> o1[1] - o2[1]);

        // 좌측부터 시작해 나뉘는 구간을 만나면 최소와 비교하여 그 합을 저장
        int baseLine = 0;
        long sum = 0L;
        for(int i=0; i<n-1; i++){
            if(set.contains(interval[i][1])){
                sum += ((long)tall[i] - tall[baseLine]);
                baseLine = i+1;
            }
        }

        // 마지막 부분의 크기 차이를 구해서 더함
        sum += ((long)tall[n-1] - tall[baseLine]);

        bw.write(String.valueOf(sum));

        bw.flush();
        bw.close();
        br.close();
    }
}