[백준 2212번] 센서 - java

문제 설명

1. 센서의 개수 N, 집중국의 개수 K가 주어진다.

2. N개의 센서에 대해 집중국을 세워야 한다.

3. 문제가 이해가지 않아 한참을 해맸다... 문제에서 구해야 하는 내용에 대해 말하자면

 

- 직선 상에 센서들이 좌표를 갖고 주어진다.

[2, 8, 10, 12, 13, 4] 요렇게 센서들이 주어지고, 만약 3개의 집중국을 세워야 한다고 해 보자

 

센서를 정렬하면 

이렇게 될 것이고, 이 중 3개의 집중국이 커버 하도록 한다면

 

 

이런 식으로 나타낼 수 있다. -> [2, 2, 1]의 범위를 커버한다.

 

풀이 과정

 1. 위의 내용을 기준으로 한번 생각을 해보면 센서들을 정렬한 후, 그 거리의 차를 구해주면 각각 센서들의 거리의 차를 구할 수 있다.

 2. 그렇다면 집중국이 커버해야 하는 최소의 거리를 구하려면 센서들의 거리의 차이가 큰 값들을 빼고 가야 할 것이다.

 3. 거리의 차이가 큰 범위 즉, 위의 내용에서 노란색에 해당하지 않는 지역을 빼 주는 방법은 다음과 같다.

먼저 [2, 4, 8, 10, 12, 13]에 대한 모든 차이를 구해준다.   ->   [2, 4, 2, 2, 1]

차이가 큰 순서대로 정렬해 준다. [4, 2, 2, 2, 1]

집중국의 개수 k개가 있다면 k-1개 만큼의 이득을 볼 수 있다.

EX)  k=1이면 무조건 [4, 2, 2, 2, 1]만큼의 거리 모두를 다 커버해야 한다. -> 4+2+2+2+1

      k=2이면 가장 긴 거리를 제외하고, 두 가지 부분으로 나누어 커버할 수 있다. -> 2+2 / 2+2+2+1

       k=3이면 처음과 같다.

  4. 이렇게 하면 k개의 집중국이 주어지는 경우, 가장 긴 순서대로 k-1개의 거리를 없애 줄 수 있다는 것을 알 수 있다.  

  5. 그리고 중요한 것이 k가 무조건 n보다 적는 이야기가 나타나지 않는다. 그렇기 때문에 k가 n보다 크거나 같다면, 그냥 0을 출력하도록 코드를 추가해 주어야 할 것이다.

코드

개인적으로 문제를 이해하기도 어려웠고 풀이를 생각하는 데에도 애를 먹었다... 그리디에 관한 공부가 더 필요할 것 같다.