Baekjoon #2212 센서

#2212 센서

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개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

---

단순한 그리디 알고리즘문제이다.

 

문제를 이해하는데 시간이 좀 걸렸고, 직선을 손으로 직접 그리기 전까지 풀이 방법을 생각하기 어려웠다.

 

---

풀이

직선에 센서를 배치하고 센서간의 거리를 먼저 구한다.

여러가지 거리가 나오는데 이 거리들 내에서 집중국을 설치해야한다.

 

최단 거리로 하려면 센서와 센서 간의 거리가 가장 긴 거리를 빼가면서 설치하면 된다. (그리디)

(가장 거리가 큰 것을 제외하는 것이 답에 가까워진다.)

 

정렬은 Arrays 클래스의 sort를 이용했고, 삽입할 때의 정렬은 Treeset으로 이용하였다.

---

전체 코드

/*
* 센서
* https://www.acmicpc.net/problem/2212
* */

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

public class P2212 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); // number of censors
        int K = Integer.parseInt(br.readLine()); // number of concentrator

        TreeSet<Integer> censors = new TreeSet<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        while (st.hasMoreTokens()) {
            censors.add(Integer.parseInt(st.nextToken()));
        }

        int[] dist = new int[censors.size() - 1];

        Iterator<Integer> iterator = censors.iterator();
        int start = iterator.next();
        int idx = 0;
        while(iterator.hasNext()) {
            int t = iterator.next();
            dist[idx++] = t - start;
            start = t;
        }

        Arrays.sort(dist);

        /*for (int i=0; i<dist.length; i++) {
            System.out.print(dist[i] + " ");
        }
        System.out.println();*/

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

        wr.write(String.valueOf(sum));
        wr.flush();
        br.close();
    }
}