[BOJ] 2212 센서

문제 링크

밤낮이 아예 바뀌었는지.. 잠이 하나도 안온다.

오늘은 그리디 문제를 풀었다. 처음엔 문제가 이해가 잘 안가서 무슨 소리지..? 집중국을 어디에다 세운다는거지? 했는데 어디에 세우는지는 중요치 않고 그냥 연속된 센서들간의 거리가 중요한 문제였다.

센서의 위치를 입력을 받을 때 중복되는 것이 있다면 한 개만 저장되게 벡터에 담은 뒤 오름차순으로 정렬했다. 이 벡터의 원소개수를 M개라고 하자.

그리고 연속되게 있는 센서들 간의 거리를 구해서 dist 벡터에 담았다. dist벡터의 크기는 M-1이 된다.

아래 그림은 문제 링크에 예제 1 상황을 그림으로 나타낸 것이다. 빨간색 점이 센서의 위치, 노란색 숫자가 이웃한 센서간의 거리이다.

파란색 타원이 집중국의 수신 가능 거리를 최소로해서 각각의 집중국이 커버하는 영역이다. 예제에서 집중국을 2개 세우므로 영역도 2개이다.

그림에서 보면 영역이 2개이므로 영역 사이에 끊기는 구간이 1개 존재하는 것을 알 수 있다. (위 그림에서는 3에서 6사이가 끊기는 구간이다.)

만약 집중국을 3개 세울 수 있으면 사이에 끊기는 구간이 2개, K개 세울 수 있으면 끊기는 구간이 K-1개 발생할 것이다.

즉 dist 배열에 들어있는 수중에서 최대 K-1개를 버리고 더하면 그게 집중국의 수신 가능 거리의 합이된다. 그런데 수신 가능 거리를 최소로 해야하므로 큰 것부터 K-1개를 버리면되고, 그 말은 작은 것부터 (M-1) - (K-1) = M - K개를 선택해 더하면 그게 답일 것이다.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K; cin >> N >> K;

    vector<int> v;
    bool check[2000005];
    fill(check, check+2000005, false);

    for(int i=0; i<N; ++i) {
        int a; cin >> a;
        if(check[a + 1000001] == true) continue;

        check[a + 1000001] = true;
        v.push_back(a);
    }

    sort(v.begin(), v.end());
    vector<int> dist;
    for(int i=1; i<v.size(); ++i) {
        int a = v[i] - v[i-1];
        dist.push_back(a);
    }

    sort(dist.begin(), dist.end());


    long long ans = 0;
    int m = v.size() - K;

    for(int i=0; i<m; ++i) {
        if(i >= dist.size()) break;
        ans += (long long)dist[i];
    }

    cout << ans << '\n';
    return 0;
}

+처음에 계속 Out of bound로 런타임에러가 떠서 애를 먹었었는데, 보니까 센서 위치의 절댓값의 범위가 1000000까지여서 음수도 가능했는데 그걸 못보고 check배열(중복을 확인하는 배열)을 check[1000001]이렇게 해서 그랬던 거였다.