백준 13164 행복 유치원 자바

문제 링크는 다음과 같다.
https://www.acmicpc.net/problem/13164

풀이는 아래와 같다.

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 st1 = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st1.nextToken());
        int K = Integer.parseInt(st1.nextToken());

        int[] baby = new int[N];

        StringTokenizer st2 = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < N ; i++) {
            baby[i] = Integer.parseInt(st2.nextToken());
        }

        int[] diff = new int[N-1]; //오름차순으로 정렬되어있는 애기들의 키를 자기보다 앞쪽의 애기와 키차이를 비교해서 넣을예정.

        for(int i = 0 ; i < N-1 ; i++) {
            diff[i] = baby[i+1] - baby[i];
        }

        Arrays.sort(diff);

        //잘 생각해보면, baby가 아기1키 아기2키 아기3키 아기4키 아기5키 이런식으로 있다면,
        //diff는 아기2-아기1, 아기3-아기2, 아기4-아기3, 아기5-아기4 이런식으로 들어가게 됨.
        //키 차이가 클수록 나가는 돈이 커지니까, 우리는 키 차이의 최솟값을 찾아야 함.
        //그래서 가장 키차이가 크게나는 쪽을 찢어줄 예정.
        //(diff를 sort후 가장 큰값 K-1개를 빼주면, K개의 집합이 나오고, 작은값 N-K+1개를 더해주면 sort 한 이후이더라도
        // 집합에서 가장 큰 아기 - 집합에서 가장 작은 아기 의 값(diff의 원소값 몇개의 합)은 K개 전부 더해진다.)
        // 바로 윗줄이 이해가 안간다면, abcd 값을 sort해서 adcb를 하더래도, a+b+c+d = a+d+c+b 이기 때문.

        int answer = 0;
        for(int i = 0 ; i < N-K ; i++) {
            answer += diff[i];
        }


        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

}

이해하면 쉬울 내용
1. 모든 키차이를 구한다. (문제의 조건에서 정렬되어서 제공.)
2. 해당 키차이를 정렬한다. (키차이가 크면, 해당 사이를 찢어줄 예정)
3. K개의 무리를 만들기 위해서는, K-1번 찢어줘야 하므로, 2번에서 정렬해준 키차이에서, 가장 큰 K-1개를 빼고 전부 더해준다.

생각해보자.
아기 다섯명이 있다 (이하 12345순서, 키순으로 정렬되어있음)
각각 자신의 앞 친구와의 키차이를 넣은 배열을 만들거다.

for(int i = 0 ; i < N-1 ; i++) {
            diff[i] = baby[i+1] - baby[i];
        }

나는 두 무리로 나눌거고, 3과 4의 키차이가 가장 크다고 하자.
그러면 아기 3과 4를 무조건 다른 무리로 떼어놓아야 하고,
아기 123, 45로 무리지어야 한다.
그럼 아기 123 무리에서 반티 값이 나오고
아기 45 무리에서 반티값이 나온다.
해당 두 무리의 반티값은, 아기3-아기1 + 아기5-아기4 이다.
아기3-아기1 + 아기5-아기4 = 아기3-아기2 + 아기2-아기1 + 아기5-아기4
위의 2번에서, 키차이를 정렬했으면,

 Arrays.sort(diff);

키차이 배열의 맨 끝은 아기4 - 아기3 (3과 4의 키차이가 가장 크므로) 이다.

diff[N-2] 값이 아기4-아기3

키차이 배열에서 가장 큰 한개(두개로 무리를 나눌거라서 하나만 빼줌, 아기3과 아기4를 다른 무리로 찢는다고 생각.) 값을 빼고 전부 더하면,

for(int i = 0 ; i < N-K ; i++) {
            answer += diff[i];
        }

위의
아기3-아기2 + 아기2-아기1 + 아기5-아기4
즉, 위의 값은 우리가 찾던 아기3-아기1 + 아기5-아기4 가 된다.

이 값이 나온다. 이제 좀 느낌이 오나..?