📌 코딩테스트 준비 :: 백준_13164:: 정렬 - 행복유치원👀

문제

풀이

1. 어떻게 묶어서 차이를 계산할지 보다는 나열해서 일정한 규칙이 나오는지 확인해보면 됩니다.
2. 처음에는 수식을 어떻게 세워야할까 고민했습니다.
3. 최소를 구하는 것이기 때문에 각 숫자간 차이를 정렬합니다.
4. k묶음에서 k가 커질수록 한개 = 한묶음이 많아져서 최소 숫자가 작아집니다.
5. 이규칙을 활용해 k묶음일 때 각 숫자간 차이를 더해서 출력해주면 됩니다.

코드

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

public class Bj13164_happy {


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        //입력값 받기
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        //원생 초기화
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        int cnt = 0;
        while(st.hasMoreTokens()) {
            arr[cnt] = Integer.parseInt(st.nextToken());
            cnt++;
        }
        //숫자간 차이 초기화 
        int[] answer = new int[n];
        answer[0]=0;
        for(int i = 1 ; i < n ; i++) {
            answer[i] = arr[i]- arr[i-1];
        }
        Arrays.sort(answer);
        int sum = 0;
        for(int i = 0 ; i < n-k+1 ; i++) {
            sum += answer[i];
        }
        System.out.println(sum);

        //예를들어.. n = 5개임
        //-> 1개로 묶을 시 n, 0 1 2 2 4
        //-> 2개로 묶을 시 n - 1, 0 1 2 2
        //-> 3개로 묶을 시 n - 2, 0 1 2
        //-> 4개로 묶을 시 n - 3, 0 1
        //-> 5개로 묶을 시 n - 4, 0

    }

}