[백준/C++] 2212번 센서

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

2212번: 센서

이 문제는 문제를 읽기 조차 조금 힘들다..

간단히 설명부터 하자면, 1 3 6 6 7 9가 있을 때 기지국이 2개라고 주어진다면

기지국 1이 [1~3]을 수신하고 기지국2가 [6~9]를 수신할 때 수신가능영역이 최소가 된다!

​

이제 이 문제를 푸는 방법에 대해 알아보자.

우선 입력으로 주어진 값을 정렬해주자. 1 6 9 3 6 7 이라는 예제가 주어졌다고 하면 이를 정렬하여 1 3 6 6 7 9로 만들어준다.

그런 뒤, 1과 3 / 3과 6 / 6과 6 / 6과 7 / 7과 9 의 차이를 구해준다. 즉, 자신과 그 뒤의 값의 차이를 구하는 것이다. 일단 이 차이를 dist라고 칭하자.

dist 값들을 모아놓은 배열은 2 3 0 1 2 가 될 것이고, 이것 또한 정렬하면 0 1 2 2 3이 될 것이다. 우리는 이걸 이용해 문제를 풀 것이다.

​

왜 그런지 설명하도록 하겠다.

1 3 6 6 7 9의 예시에서 만약 집중국이 1개라면 집중국은 [1~9] 영역 모두를 수신해야하며 길이는 8이 될 것이다.

집중국이 2개라면 dist 배열의 맨 뒤(가장 큰 값)를 지워주면 된다! ★★★

집중국이 K개라면 dist 배열의 뒤에서부터 K-1 번 지워주면 된다! ★★★

​

==> 집중국이 2개일 때, dist값이 가장 큰 놈을 지워준다는 것은 아까 0 1 2 2 3 배열에서 3을 없애 0 1 2 2로 만든다는 뜻이고,

이는 집중국을 [1~3]에 하나 세우고, [6~9]에 하나 세워서 관리해주겠다는 뜻이다. (집중국을 저렇게 세우면, 3과 6을 이어주지 않아도 되어서 길이 3을 이득보기 때문이다!!)

만약 집중국이 3개라면 그다음 큰 값인 2를 지워서 dist 배열을 0 1 2로 만들고,

집중국을 [1~3], [6~7], [9] 로 세우겠다는 뜻이다. (7~9의 거리가 2이므로 집중국을 앞서 말한 것 처럼 세우면, 7과 9가 떨어지게 되므로 거리 2를 줄일 수 있게 된다.)

 

즉, 수신 가능 영역 길이의 최솟값은 dist[0]부터 dist[n-k-1]의 합이다!

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int n,k,ans;
vector<int> v,dist;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> k;

    for(int i=0; i<n; i++){
        int num;
        cin >> num;
        v.push_back(num);
    }
    sort(v.begin(), v.end());

    for(int i=0; i<n-1;i++){
        int d = v[i+1] - v[i];
        dist.push_back(d);
    }
    sort(dist.begin(),dist.end());

    for(int i=0; i<n-k;i++){
        ans += dist[i];
    }
    cout << ans;

    return 0;
}