[백준 2212번] 센서 - JAVA

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

2212번: 센서

풀이

사용한 알고리즘 : 그리디, 정렬

 

풀이전략

 

먼저 문제에 대한 이해가 어렵기 때문에 아래 그림을 통해 문제 설명부터 하도록 하겠습니다.🎨

위 그림처럼 입력받은 센서들을 오름차순으로 정렬한 뒤에,

K개의 집중국을 통해 최소 수신 가능 범위를 구하는 문제입니다.

 

이를 수학적으로 쉽게 나타내면 아래와 같습니다.

먼저 센서 간의 격차를 구한 뒤 이를 오름차순으로 정렬시킵니다.

그런데 우리는 2개의 집중국을 설치할 수 있는 상황입니다.

 

즉, 오름차순으로 정렬시킨 오차들을 2개의 집합으로 나눌 수 있다는 것입니다.

근데 센서들 간의 연결을 하나만 제외시키면 2개의 집합으로 나눌 수 있으므로

격차가 제일 큰 값 하나를 제외시킨 나머지들의 총합이 우리가 구하는 정답입니다.

 

따라서 센서의 수 N, 집중국의 수가 K일 때,

오름차순 정렬된 격차들이 담긴 배열을 처음 인덱스 값부터 N-K 개를 더하면 정답을 구할 수 있습니다.

 

제출코드

import java.io.*;
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());

        int sensor[] = new int[N];
        int gap[] = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;++i){
            sensor[i]=Integer.parseInt(st.nextToken());
        }
        Arrays.sort(sensor);
        for(int i=1;i<N;++i){
            gap[i]=sensor[i]-sensor[i-1];
        }
        Arrays.sort(gap);

        int sum=0;
        for(int i=1;i<N-K+1;++i){
            sum+=gap[i];
        }
        bw.write(sum+"\n");
        bw.flush();
        bw.close();
    }
}