[백준] 2212 센서 - Greedy / Java

• 문제 링크

2212번: 센서

 

• 풀이 과정

예제 입력 1을 예시로 1, 3 구간과 6, 9 구간에 집중국을 2개 설치 시, 수신 가능영역의 최소 길이는 2 + 3 = 5 가 된다.

이는 각각의 수신 가능한 센서를 오름차순 정렬 및 센서 간의 거리를 구해 더한 값, 0 + 1 + 2+ 2 = 5 와 같고,

이를 일반화하여 알고리즘을 풀이한다.

 

센서의 좌표를 입력받아 오름차순 정렬 후, 각 센서 간 거리를 구해 dist 배열에 저장하고, (dist[i] = arr[i + 1] - arr[i])

수신 가능영역의 최소값을 구해야 하므로 dist 배열을 오름차순 정렬한다.

 

이어서 k개의 집중국이 n개의 센서 중 수신 가능한 영역인

0에서 n - k - 1번 인덱스의 범위내의 거리 값을 누적해 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public 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());

        if (k < n) {
            st = new StringTokenizer(br.readLine());

            int[] arr = new int[n];
            for (int i = 0; i < n; i++)
                arr[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(arr);

            int[] dist = new int[n - 1];
            for (int i = 0; i < n - 1; i++)
                dist[i] = arr[i + 1] - arr[i];
            Arrays.sort(dist);

            int sum = 0;
            for (int i = 0; i < n - k; i++)
                sum += dist[i];

            bw.write(String.valueOf(sum));
        } else
            bw.write("0");

        bw.flush();
    }

}