[BOJ] 백준 2212번 : 센서 (JAVA)

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

2212번: 센서

문제

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

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

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

 

풀이

문제를 이해하는 데 시간이 좀 걸린 문제였습니다. 위 문제에서 예제는 다음과 같았습니다.

6

2

1 6 9 3 6 7

즉, 센서는 6개인데 집중국은 2개를 설치해야했습니다. 그래서 [1, 3] 경로의 집중국을 1개, [6, 9] 경로의 집중국을 1개 설치함으로써 수신 가능 영역의 최소 길이는 2 + 3 = 5가 됩니다.

이 문제를 푸는 열쇠는 그리디 알고리즘이었습니다. 먼저, 집중국이 센서의 개수보다 크거나 같은 경우를 봅시다.

그러면, 집중국은 각 센서마다 1개씩 담당하면 되므로, 수신 가능 영역의 최소 길이는 0이 됩니다.

하지만, 센서가 N개이고, 집중국이 N - 1개처럼 개수가 차이가 날 경우 어떻게 해야하는지 판단하는 것이 핵심이었습니다.

우선, 우리가 해야할 일은 센서를 오름차순으로 정렬하는 것입니다. 그리고 dif라는 배열을 정의하여 센서의 i + 1인덱스의 값과  i 인덱스의 값을 뺀 값을 넣은 후, 오름차순으로 정렬합니다.

그런 다음, 아래와 같은 로직을 코드로 작성하면 됩니다.

1. K >= N일 경우, print("0")을 출력하고 프로그램을 종료한다.

2. K < N일 경우, dif 배열의 K - N번째 인덱스의 값을 더합니다.

답을 도출해 내기 위해서 2번을 과정을 거치는 이유는 다음과 같습니다.

 

센서 하나 당 집중국 하나를 설치가 불가능한 즉, 집중국의 개수가 더 적은 상황에서는 어떤 집중국이 2개 이상의 센서를 커버해야합니다.

만약, 센서 개수가 n개, 집중국 개수가 n-1일 때, 먼저 n-1개의 집중국을 n-1개의 센서에다가 설치합니다. 그리고, 서로 붙어있는 센서 2개를 하나의 기지국이 처리하면 됩니다.

dif배열 오름차순으로 정렬했을 때, 가장 앞부분에 간격을 차례대로 집중국이 부담하는 것이 최선이라고 할 수 있습니다.

앞서 살펴본,

6

2

1 6 9 3 6 7

예제의 경우를 위 로직을 적용해서 풀어보겠습니다.

censor 배열을 오름차순으로 정렬하면, {1, 3, 6, 6, 7, 9} 이며, dif 배열을 오름차순으로 정렬하면, {0, 1, 2, 2, 3}입니다.

N은 6인데 반해 K는 2이기때문에 집중국은 4개의 센서에 대해 커버를 쳐야하는 상황입니다. 따라서, 0 + 1 + 2 + 2 = 5를 한 결과가 정답이며, 이것은 [1, 3]의 경로와 [6, 9]의 경로를 합한 것입니다.

 

위 내용을 종합하여 작성한 소스코드는 아래와 같습니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
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 Exception {
        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) {
            bw.write("0\n");
            bw.close();
            br.close();
            return;
        }
 
        int[] censor = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int temp = Integer.parseInt(st.nextToken());
            censor[i] = temp;
        }
        Arrays.sort(censor);
 
        int[] dif = new int[N - 1];
        for (int i = 0; i < N - 1; i++) {
            dif[i] = censor[i + 1] - censor[i];
        }
        Arrays.sort(dif);
 
        int ans = 0;
        for (int i = 0; i < N - K; i++) {
            ans += dif[i];
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.