[백준] 13164번. 행복 유치원(JAVA)

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

---

문제

---

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] height = new int[N];
        int[] comparison = new int[N-1];

        for(int i = 0; i < N; i++){
            height[i] = sc.nextInt();
        }

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

        Arrays.sort(comparison);

        int sum = 0;

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

        System.out.println(sum);
    }
}

 

 키로 배열된 것보다 그 차이에 따른 값을 측정한다는 것에 중점을 뒀다. 

 

문제의 예시를 따르면 1 3 5 6 10을 이용하기보다는 2 2 1 4로 변환한다. 이 후 3개의 그룹을 나눠야 한다는 것은 이 중 2개의 값을 제외할 수 있음을 의미하고, 최종적으로 남은 값을 더하면 되기 때문에 이 배열을 다시 정렬하여 최대값 K-1개를 제외하면 된다는 것이다. 이 때 i에 대한 반복 범위가 중요하다. K-1개라고 해서 단순히 i < N -(K-1)을 하게 되면 예시의 경우 i < 5 - (3-1) 즉, i < 3의 범위로 들어가 0, 1, 2의 인덱스에 대한 값을 갖기 때문에 i < N - K로 바로 입력해주어야 한다.