[2212] 센서

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

2212번: 센서

n개의 데이터를 k개의 집합으로 분할하고 분할된 각 집합의 (최대값)-(최소값)의 총합을 최소화하는 문제이다.

6 

2

1 6 9 3 6 7

입력이 위와 같을때, 센서들의 위치를 정렬한 뒤 중복을 제거하면 아래와 같다.

1 3 6 7 9

이를 {1, 3}, {6, 7, 9}처럼 분할하면 (3-1)+(9-6)=5의 최적해를 얻을 수 있다.

또한, k>=n인 경우에는 모든 데이터를 크기가 1인 집합으로 분할 할 수 있기에

최대값==최소값이 되고, 이에 따라 최적해는 0이 된다.

 

읽어보면 마치 집중국을 어디에 배치해야 하는지가 관건인 것처럼 보이기도 하는데, 이문제는

집중국의 위치는 전혀 중요하지 않다.

집중국의 위치가 중요한 문제라면, 문제는 다음과 같은 형태여야 한다.

1. 초기 상태의 집중국은 근처의 거리 d이하로 떨어진 센서와 통신할 수 있다.

즉, 집중국의 위치가 p라면, [p-d, p+d]사이의 센서는 비용 없이 항상 통신이 가능하다.

2. 집중국을 한 번 업그레이드 하면, 해당 집중국이 통신할 수 있는 거리가 1 증가한다.

-> 모든 센서에 통신이 가능하도록 만들기 위해 필요한 업그레이드 횟수의 최소값은 얼마인가?

 

 

이 문제를 그리디하게 해결하기 위해서 데이터를 정렬하고 다음번 센서까지 거리가 가장 먼 센서를 찾아

해당 센서를 분할된 집합의 마지막 원소로 삼으면 된다.

시작 원소는 초기상태에는 arr[0]가 될것이고, arr[3]이 그리디한 탐색 결과로 선정되었다면,

{arr[0], arr[1], arr[2], arr[3]}처럼 만들어주고, 다음에는 {arr[4] ~ arr[target]} 에서 target을 찾으면 된다.

이를 코드로 구현하면 아래와 같다.

for (i = 0; i < startSize - 1; i++) {
    int s = start[i];
    int e = start[i + 1] - 1;
    answer += (num[e] - num[s]);
}

 

한가지 유의할점은, {arr[0]~arr[3]}같이 이미 분할된 집합 안에서도 항상 추가적으로 분할될 가능성이 있다는 것이다.

 

모든 가능성을 열어두고, 다음 센서까지의 거리가 가장 긴 센서를 찾기 위해, 우선순위큐를 사용할 수 있겠다.

우선순위큐에는 arr[1]-arr[0], arr[2]-arr[1]    ...    arr[n-2]-arr[n-3], arr[n-1]-arr[n-2]의 n-1개의 거리의 차이를 넣어두고,

최종적으로 답을 계산하기 위해서는 각각의 집합이 어떠한 상태인지를 알아야 하기에

거리와 함께 인덱스까지 넣어준다.

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n, k;
priority_queue<pair<int, int>>q;
vector<int>num;
int main(void) {
    int i, j;
    scanf("%d", &n);
    scanf("%d", &k);
    if (k >= n) {
        printf("0");
        return 0;
    }
    for (i = 0; i < n; i++) {
        int P;
        scanf("%d", &P);
        num.push_back(P);
    }
    sort(num.begin(), num.end());
    num.erase(unique(num.begin(), num.end()), num.end());
    int numSize = (int)num.size();
    for (i = 1; i < numSize; i++) {
        q.push({ num[i] - num[i - 1],i });
    }
    vector<int>start;//집합의 시작 인덱스
    start.push_back(0);//항상 0부터 시작
    for (i = 1; i <= k - 1; i++) {//k개의 집합 <-> k-1번의 분할
        pair<int, int>cur = q.top();
        q.pop();
        start.push_back(cur.second);
    }
    int startSize = (int)start.size(), answer = 0;
    for (i = 0; i < startSize - 1; i++) {//마지막 집합 제외
        int s = start[i];
        int e = start[i + 1] - 1;
        answer += (num[e] - num[s]);
    }
    int s = start[startSize - 1];//마지막 집합
    int e = numSize - 1;
    answer += (num[e] - num[s]);
    printf("%d", answer);
    return 0;
}

k>=n인 경우, 우선순위 큐의 크기는 n-1인데, 여기에 k번을 pop하게되면 큐가 비어있을때에도 pop하게 된다.

큐가 비어있을때에 break하도록 하거나, 조기에 프로그램을 종료하면 된다(12-15라인)

22라인은 중복된 원소를 제거하기 위해 사용했으나, 꼭 필요한 부분은 아니다.