백준 2212 [자바] java 센서

문제 링크: https://www.acmicpc.net/problem/2212

2212번: 센서

 

▶문제

한국 도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능 영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능 영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

---

▶입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

---

▶출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

---

▶해설

문제를 이해하는데 시간이 더 오래걸린 문제입니다.

 

센서는 좌표상에 정수로 존재합니다. 이때 집중국을 세워서 집중국과 연결된 센서들의 거리가 최소를 구하는 것입니다. 

 

예제처럼 1 6 9 3 6 7이라면

 

좌표상 1 3 6(2) 7 9로 존재하는 것입니다. 이때 특정 위치에 집중국을 세워 센서가 최소한 하나의 집중국과 연결하고 그 값들의 합이 최소를 목표로 합니다. 

 

만약 1과 7에 집중국을 세웠다면, 1~3= 2   6~7=1 7~9=2 가 되는 것입니다.

3은 9보다 1이 더 가깝고, 6과 7은 1보다 9가 더 가깝기 때문에 가까운 것을 연결하면 됩니다. 

 

1. 센서들의 좌표를 오름차순으로 정렬합니다.

2. 센서들 인근에 위치한 값의 차이를 list에 저장합니다.

3. 해당 list를 내림차순으로 정렬합니다.

4. k-1 ~ n-1까지 의 list의 값을 더해줍니다.

 

4번처럼 하는 이유는 다음과 같습니다.

 

ex) 센서 4개 집중국 2개 1 5 10 12(센서 위치)

 

집중국이 1일 때

집중국을 어디 세우던지, 모든 센서를 연결하기 위해 모든 차이 값을 더해야 합니다.

 

집중국이 2일 때

가장 큰 차이를 가진 센서를 다르게 연결하면 최솟값이 됩니다.

집중국을 (1,10), (5,12), (5,10), (5,12)에 세운다면 5~10까지의 가장 큰 값인 5를 제외할 수 있습니다.

 

집중국이 3일 때 

(1,5,10), (1,5,12)로 세운다면 그다음 큰 차이를 가지는 1~5의 값을 제외할 수 있습니다.

 

이렇게 가장 큰 값을 빼면서 진행하기 때문에 k-1~n-1의 범위를 가지는 것입니다. 

 

(단 집중국의 수가 센서의 수보다 크거나 같다면 바로 0을 반환해줍니다.)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int n, m;
    static List<Integer> list;
    static int result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());

        if(m>=n){
            System.out.println(0);
            return;
        }
        list = new ArrayList<>();

        String[] s = br.readLine().split(" ");
        for(int i=0; i<n; i++){
            list.add(Integer.parseInt(s[i]));
        }
        Collections.sort(list);
        solve();
        System.out.println(result);
    }

    private static void solve(){
        List<Integer> deg = new ArrayList<>();
        for(int i=0; i<n-1; i++){
            deg.add(list.get(i+1)-list.get(i));
        }

        Collections.sort(deg, Collections.reverseOrder());

        for(int i=m-1; i<n-1; i++){
            result+=deg.get(i);
        }

    }
}