[백준](Java) 2212 - 센서

문제 링크

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

문제 풀이

자력으로는 못푼 문제였다. 그리디 알고리즘으로 접근해야 겠다는 생각만 들었고 그 외에 접근을 어떻게 해야할지를 몰랐다. 송전탑들의 위치를 오름차순으로 정리를 하고나서 거리의 합이 최소가 되는 지점을 K개를 찾아야 했는데 이 부분에 대한 접근 방법이 부족했었다.

1. 송신탑들을 우선 오름차순으로 정렬한다.

Arrays.sort(arr);

2. 송신탑들끼리의 거리를 구한다.(거리는n-1개가 나온다.)
   (ex)송신탑 1 3 6 의 거리 -> 2 3

int [] len = new int[n-1];
        for(int i=0; i<len.length; i++){
            len[i] = arr[i+1]-arr[i];
        }

3. 송신탑들끼리의 거리를 정렬한다.

        Arrays.sort(len);

4. 1 3 6 6 7 9 의 경우 2 3 0 1 2 가 나오게 되며
   이를 정렬하면 0 1 2 2 3 이 나오게 된다. ex) 6 6 사의 거리는 0, 3과 6 사이의 거리는 3이된다. 여기서 중계탑(k)를 2개 놓게 될때 거리의 합이 최소가 되려면 3 6에다가 놓게 되면 3의 거리가 0이 되므로 0 + 1 + 2 + 2 = 5가 되어 최솟값이된다.

이를 위에 배열에 적용시켜보면 len의 길이에 (k-1)을 한것까지만 더해주게 되면 최솟값이 나오게 된다.

        for(int i=0; i<len.length-(k-1); i++){
          sum+=len[i];
        }

코드

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 sum = 0;
        int [] arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = (sc.nextInt());
        }
        Arrays.sort(arr);
        int [] len = new int[n-1];
        for(int i=0; i<len.length; i++){
            len[i] = arr[i+1]-arr[i];
        }
        Arrays.sort(len);
        for(int i=0; i<len.length-(k-1); i++){
          sum+=len[i];
        }


        System.out.println(sum);

    }
}