[백준] 2212 센서 - JAVA

★★★☆

문제

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

2212번: 센서

풀이시간 : 30분

풀이

문제 설명이 이해가 가지 않아서 조금 헤멘 문제이다.

N개의 센서가 어떤 거리에 위치해 있고, 우리는 그 거리에 집중국을 세워야 한다.

K개의 집중국으로 N개의 센서를 모두 커버해야 하는데, 각각의 집중국들은 정해진 최대 거리가 없다!

( 집중국마다 최대 거리를 다르게 설정 할 수 있다)

집중국을 세울 때 각각의 집중국들의 설정 거리의 합이 최소가 되게끔 집중국을 세우는 게 목적이다. 

 

먼저 우리가 할 일은 N개의 센서를 K개의 그룹으로 나누어야 한다.

K개로 나눌 때, 어떤 기준으로 나누느냐가 관건인데, 집중국이 커버하는 거리, 즉 각 그룹에 속하는 센서들의 간격을 최소화하면 되기 때문에 센서간의 거리가 가장 긴 곳들부터 가르면 되지 않을까? 라고 생각했다.

 

처음 알고리즘은 다음과 같았다.

 

1. 먼저 센서들을 위치 순서대로 정렬한다. 

2. 센서간의 간격을 구해 리스트에 저장한다.

3. 간격을 내림차순으로 정렬한 후, 앞에서부터 K개만큼 지운다.

4. 나머지 간격들의 값을 더한 후 출력한다.

 

위 방식대로 풀었더니 런타임에러가 발생했다. 집중국의 개수(K)가 N과 같거나 더 많을 경우가 존재했기 때문이다!

 

그래서 아래의 알고리즘으로 바꾸고 잘 통과했다.

 

1. 센서들을 위치 순서대로 정렬한다.

2. 센서간의 간격을 구해 리스트에 저장한다.

3. 간격을 오름차순으로 정렬한 후 , 앞에서부터 N-K개만큼 값을 더한다.

4. 해당 값을 출력한다.

코드

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

public class Main {

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] sensors = new int[N];

        for (int i = 0; i < N; i++) {
            sensors[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sensors);

        ArrayList<Integer> gap = new ArrayList<>();

        for (int i = 0; i < N-1; i++) {
            gap.add(sensors[i+1]-sensors[i]);
        }

        Collections.sort(gap);

        int answer = 0;
        
        for (int i = 0; i < N-K; i++) {
          answer+=gap.get(i);
        }

        System.out.println(answer);
    }


}