백준 2212 - 센서

문제 설명

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 센서가 있을 때 K개의 집중국을 세울 계획이다.

이때, K개의 집중국의 수신거리가 최소로 나오도록 설치할 때 수신거리의 총합을 구해야 한다.

 

수신거리가 최소가 되려면 센서들이 최대한 밀집되어 있어야 한다.

센서 사이의 거리가 수신국의 수신 거리와 일치하기 때문이다.

예를 들어 보자.

1과 3에 센서가 있고 2에 집중국에 설치한다고 치면, 1-2, 2-3 으로 총 2의 수신거리가 필요하다.

이는 1과 3 사이의 거리와 일치한다.

 

하지만 모든 센서 사이의 거리가 수신거리가 되는 것은 아니다.

센서는 하나의 집중국에만 송신하면 되기 때문에 그룹화가 가능하다.

즉, 다른 그룹에 속하는 센서 사이의 거리는 수신 거리가 되지 않는다.

집중국이 2개라고 한다면 초록색 그룹과 파란색 그룹으로 분리할 수 있다.

이때, 3과 6사이의 거리는 수신하는 집중국이 다르기 때문에 수신 거리에 포함되지 않는다.

 

즉, 센서 사이의 거리가 집중국의 수신거리가 되는데 그룹화를 잘하면 몇 개의 거리는 포함하지 않을 수 있다.

그럼, 최대한 긴 간격을 포함하지 않으면 되는 것이다.

이때, 포함하지 않을 수 있는 개수는 집중국의 개수(K) - 1개이다.

집중국 사이의 거리가 생기는 것이기 때문에 K개간의 사이인 K-1이 되는 것이다.

 

정리하자면, 센서 사이의 거리가 집중국의 수신거리가 되며 K-1개는 배제하고 고를 수 있다.

따라서, 센서사이의 거리를 정렬한 뒤 K-1개를 제외한 작은 간격을 모두 더하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, K;
vector<int> sensors;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N >> K;

    sensors.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> sensors[i];
    }

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

    vector<int> gaps;
    for (int i = 0; i < N-1; i++)
    {
        gaps.push_back(sensors[i + 1] - sensors[i]);
    }

    sort(gaps.begin(), gaps.end(), greater());

    int ans = 0;
    for (int i = K - 1; i < N-1; i++)
    {
        ans += gaps[i];
    }

    cout << ans;

    return 0;
}

---