[C++] 백준 2212: 센서

문제 이해

- 도로에 센서와 그것을 관리할 집중국을 설치할 예정이다.

- 센서는 적어도 하나의 집중국과 통신이 가능해야 한다.

- 각 집중국은 수신 가능 영역을 조절할 수 있다.

 

<입력>

- N: 센서의 개수 (1 ~ 10,000, 10^4)

- K: 집중국의 개수(1 ~ 1,000, 10^3)

 

<출력>

- 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 구하여라.

 

 

문제 풀이

문제에서 원하는 것은

N개의 센서가 있을 때, 이들을 K개의 영역(집중국의 영역)으로 나누는 것이다.

그럼 수신 가능 영역의 길이의 합이 최소가 되도록 K개의 영역으로 어떻게 나눌까?

 

 

센서들을 K개의 영역으로 나누면 K-1개의 영역 사이의 구간이 생긴다.

센서들끼리의 거리를 먼저 구한 뒤, 거리가 먼 k-1개의 구간을 영역 사이의 구간으로 하면 되지 않을까??

 

 

즉, n개의 센서끼리의 거리를 구한 뒤 정렬하여 값이 큰 k-1개를 제외하고 더해주면

문제에서 원하는 답이 되는 것이다.

 

 

예를 들어

예제의 

6
2
1 6 9 3 6 7

같은 경우는

 

1 3 6 6 7 9로 정렬될 수 있고,

(1 3) (6 6 7 9)로 나뉘는 게 최선이다.

 

이때 각 센서끼리의 거리를 보자.

2 3 0 1 2 이고,

 

k가 2이므로 2개의 영역으로 구분해야 한다는 뜻이며,

1개의 영역 사이의 구간이 존재한다는 뜻이다.

 

센서 사이의 거리 중 제일 큰 3을 영역 사이의 구간으로 하면

우리가 임의로 나눴던

(1 3) (6 6 7 9)와 동일하게 나뉘게된다!!!

 

센서 사이의 거리 중 값이 제일 큰 3을 제외하고 0 1 2 2끼리 더하면 5로 예제의 출력과 동일하다.

 

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

int n, k, ans = 0;
vector <int> pos, diff;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n>>k;
    for(int i = 0; i < n; i++){
        int tmp;
        cin>>tmp;
        pos.push_back(tmp);
    }

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

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

    int size = diff.size();
    for(int i = 0; i < size - k+1; i++){
        ans += diff[i];
    }

    cout<<ans;
    return 0;
}