[Day18]JAVA 백준 센서(2212번)

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

 
백준 2212번 문제를 풀기위해서는 Greedy 알고리즘을 활용하여 해야한다.

---

🌘문제 이해하기

N개의 센서  K개의 집중국 , 각 집중국의 수신 가능영역 거리의 합의 최솟값을 구하는 문제 

 
집중국의 수신 가능영역이란  범위라고 생각하면 된다. 
6 과 9 사이의 집중국을 세우면 수신 가능영역은 9 - 6 = 3 이고 
13과 21 사이의 집중국을 세우면 수신 가능영역은 21 - 13 = 8 이다.
 
즉, 수신 가능영역을 최대한 작게 만들어 집중국을 세우는 것이 문제의 중요 포인트인다. 

---

🌗문제 자세히보기
 
첫번째 예시로 문제를 해결해 보겠다. 

- 센서(N) :  6개
- 집중국(K) : 2개
- 센서가 있는 좌표 : 1 6 9 3 6 7

 
센서가 있는 좌표를 정렬해서 보면 아래 그림과 같다. (1 , 3 , 6 , 6 , 7 , 9 )

 
센서와 센서 사이의 거리를 계산해 보면 ( 2 , 3 , 0 , 1 , 2 ) 이다.
센서 사이의 공간의 개수는 : 5개 (N -1)

 
집중국을 노랑색 부분에 세운다고 하면 집중국 사이의 공간은 1개이다.
집중국 사이의 공간의 개수는 : 1개(K-1)

즉 이 1 공간 부분은 집중국을 세울 범위에 적합하지 않은 범위이다.
 
센서 사이 사이의 공간(5) 중 적합하지 않은 범위의 개수(1) 개수 만큼 제거하면 집중국을 세우는 적합한 범위만 남게 된다. 
반대로 생각하면 작은 범위부터 집중국을 세우기 적합한 범위를 더하면 된다. 

 
집중국2개는 (1~3) , (6~9) 사이에 세울 수 있으며 , 수신가능한 최솟값은 
1~3 : 2
6~9 : 3 
총 합은 2+3 = 5 가 된다.  

 

---

🌖문제 해결하기 
센서 : N , 집중국 : K , 센서 공간 개수 : N-1 , 집중국 공간 개수 : K-1

1. 입력받은 센서 좌표를 오름차순으로 정렬한다.
2. 센서 좌표 사이의 거리를 계산한다.(배열에 저장)
3. 센서 좌표의 거리를 오름차순으로 정렬한다.
4. 센서 사이 공간 개수(N-1) 를 집중국 사이 공간 개수(K-1)를 제거한 수만큼 (N-1) - (K-1) = N - K ,
센서 좌표의 거리를 작은 수부터 N-K 수 만큼 더해준다.

 

---

🌕 최종코드

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException
    {        
        int answer =0;

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        //센서 수
        int N = Integer.parseInt(br.readLine());

        //집중국 수 
        int k = Integer.parseInt(br.readLine());

        //센서 좌표
        Integer[] sensor = new Integer[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0;i<N;i++)
        {
            sensor[i] = Integer.parseInt(st.nextToken());
        }

        if(N==k)
        {
            System.out.println("0");
            return;
        }

        //센서 좌표 오름차순
        Arrays.sort(senser);

        //센서 사이 사이 거리 저장
        Integer[] sensorLength = new Integer[N-1];
        for(int i=0;i<N-1;i++)
        {
           int len = sensor[i+1] - senser[i];
           sensorLength[i] = len;
        }

        //센서 사이 거리 오름차순
        Arrays.sort(sensorLength);
        
        for(int i=0;i<N-k;i++)
        {
            answer +=sensorLength[i];
        }

        //센서 사이 거리 중 집중국 사이거리k-1 만큼 제외 하기        
        System.out.println(answer);
    }        
        
}