99클럽 코테 스터디 18일차 TIL (2212번: 센서)

문제

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

---

학습 키워드

• 그리디

 

시도

• (실패) 해결 방법을 찾지 못함
• (성공) 다른 사람 해석을 이해하고 작성

 

풀이 및 코드

1. 각 센서의 위치를 정렬 한다.
   • 1 6 9 3 6 7 -> 1 3 6 6 7 9
2. 센서간 거리를 계산한다.
   • 1 3 6 6 7 9 인 경우, 센서 간 거리는 2 3 0 1 2 가 된다.
3. 집중국은 최대 K개 세울 수 있기 때문에 K - 1 개의 거리가 먼 센서 간의 거리를 제외한 나머지의 합을 구한다.
   • 센서 간 거리가 2 3 0 1 2 이므로, 정렬하면 0 1 2 2 3이 된다. 여기서 K=2 인 경우, 1개만 제외하면 되므로 3을 제외하면 0 1 2 2 의 합인 5가 정답이 된다.

 

아래 그림 설명을 보면, 집중국이 2개(K) 세울 수 있으므로 가장 먼 거리 1개(K - 1)을 제외하면 두 구간으로 분리가 된다.

그림 설명

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

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

       int N = Integer.parseInt(br.readLine());
       int K = Integer.parseInt(br.readLine());

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

       Arrays.sort(arr);
       int[] diff = new int [N - 1];
       for (int i = 0; i < N - 1; i++) {
          diff[i] = arr[i + 1] - arr[i];
       }

       Arrays.sort(diff);
       int answer = 0;
       for (int i = 0; i <= N - 1 - K; i++) {
          answer += diff[i];
       }
       System.out.println(answer);
    }
}