[C++] 센서 (2212번)

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

2212번: 센서

---

문제풀이

 

사고력이 필요한 문제다.

문제를 간단히 요약해보면, N개의 센서가 정수 좌표이 있으며 중복해 있을 수 있다. K개의 집중국이 있고 집중국은 아무데나 놔도 되고 모든 센서를 수신하면서 수신 가능영역이 최소인 위치에 놓아야 한다.

 

 

문제 접근은 이런 방식으로 해 보았다.

 

센서가 이리저리 놓여있을 텐데, 어느 지점 마다 끊어서 집중국을 설치해야 할까?

센서 사이의 거리가 먼곳은 집중국을 분리해서 설치하는게 좋을것 같다.

 

그럼 거리가 먼곳은 어떻게 알 수 있을까?

아! 센서를 정렬해서 거리를 구한뒤 그 거리를 정렬하면 거리가 먼곳을 알 수 있겠네?

그럼 가장 먼 곳을 빼면 최소 거리를 구할 수 있을것같은데?

 

그리고 예시를 보고 적용해 보았다.

정렬 : 1 3 6 6 7 9

 

거리 차 정렬: 0 1 2 2 3

일단 거리가 가장 많이 차이나는 3 과 6 쪽을 분리해보자. 그럼 1~3에 집중국을 하나 설치하는 것이고, 6~9에 집중국을 하나 설치하는 것이다. 잘 이해 안되면 그림으로 그려보는걸 추천한다.

 

집중국은 아무데나 설치할 수 있으므로 중간에 설치하게 되면 1~3은 2, 6~9는 3이되어 합을 구하면 정답인 5가 된다.

이를 생각한 뒤 거리차 정렬을 다시보면, 3을 제외한 모든 수를 더한 값이 된다.

 

어떻게 분리하던간에 집중국은 각 분리된 지점의 중간에 위치하므로 그냥 남은 거리의 합을 구하면 정답이 되는 것이다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10000];
int arr2[10000];

int main() {
    int n, k;
    cin >> n >> k;

    for(int i=0; i<n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr+n);

    for(int i=1; i<n; i++) {
        arr2[i-1] = arr[i] - arr[i-1];
    }

    sort(arr2, arr2+n-1);

    int answer = 0;

    for(int i=0; i<n-k; i++) {
        answer += arr2[i];
    }

    cout << answer;
    return 0;
}

거리 차의 개수이기 때문에 차이를 담는 배열은 n-1개가 되고, 집중국 개수 - 1 만큼 차이가 큰 값을 합에서 제외해야 하기때문에,

n-1-(k-1) -> n-k 개의 차의 합을 순서대로 더해주면 답이 되는 것이다.