본문 바로가기

백준

[백준/JAVA] 2212번: 센서

문제 보러가기

 

2212번: 센서

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

www.acmicpc.net

[알고리즘]

1. 센서의 위치를 입력받고 오름차순으로 정렬한다.(int[] sensors)

2. 앞센서와 뒷센서간의 간격을 저장 후 오름차순으로 정렬한다.(int[] distance)

3. 맨 처음의 센서(sensors[0])과 맨 마지막 센서(sensors[N-1])의 간격을 저장한다.

4. 3번에서 저장한 값에서 distance의 가장 큰값부터 차례대로 K-1번 빼준다.

5. 4번에서 구한값을 출력한다.

 

[문제풀이]

이번 문제는 주어진 값의 배열에서 K개의 부분 집합으로 나누는 문제이다.

나누어진 부분 집합의 간격을 최소한으로 줄여야한다.

1 3 6 6 7 9

우선 센서를 입력받아 오름차순으로 정렬하였다.

여기서 예시로서, K=3이라고 하자.

그렇다면 센서 배열을 3개로 나눌 수 있는데, {1} , {3}, {6, 6, 7, 9}로 나누는 것이 최선의 방법이다.

여기서 힌트는 부분 집합의 간격이다. {1} 과 {3}의 차이는 2이고, {3} 과 {6, 6, 7, 9} 의 간격은 3이다.

즉, 간격이 큰 것부터 나누어 준다면 정답을 구할 수 있다.

 

그 방법으로서 먼저 처음 센서와 맨 끝단의 센서의 간격을 저장한다. ( 9 -1 = 8)

그리고 앞 센서와 뒷 센서간의 간격의 차이를 배열로서 저장한다. 

2 3 0 1 2

그리고 센서간의 간격을 내림차순으로 정렬한다.

3 2 2 1 0

간격의 최대값(3)에서부터 K-1번까지 더해서 처음 센서와 맨 끝단의 센서의 간격(8)에서 빼준다.

그렇다면 8 - 3 - 2 로서 정답은 3이 된다. 예시에서는 K가 2이기 때문에 3만 빼주게 되면 8 -3 = 5이다.

 

[코드]

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int K = Integer.parseInt(br.readLine());
        int[] sensors = new int[N];
        int[] distance = new int[N - 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) sensors[i] = Integer.parseInt(st.nextToken());
        Arrays.sort(sensors);
        for (int i = 0; i < N - 1; i++) {
            distance[i] = Math.abs(sensors[i + 1] - sensors[i]);
        }
        Arrays.sort(distance);
        int answer = sensors[N - 1] - sensors[0];
        int index = N - 2;
        for (int i = 0; i < K - 1; i++) {
            if (index < 0) break;
            answer -= distance[index--];
        }
        bw.write(answer + "");
        bw.close();
    }
}

'백준' 카테고리의 다른 글