[개쉬운 풀이] 백준 2212 센서 (CPP/C++)

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

2212번: 센서

생각 

처음 든 생각은 집중국이 무조건 정수 위에 있어야 한다는 생각이다. 하지만 문제를 잘 읽어보면 그런 말이 없고 그냥 구간을 구하는 문제이다.

해당 고정관념만 벗어난다면 아주 쉽게 해결할 수 있다.

우리는 보통 집중국을 선택할 때 센서들의 군집별로 가장 가까운 곳에 집중국을 놔야 최소 거리를 구할 수 있다고 판단할 수 있다.

따라서 나온 결론은 다음과 같다.

1. K개의 집중국이 있다면 우리는 센서들을 K개의 군집으로 묶을 수 있다. 

2. 군집을 살펴보면 [6 ~ 9]에서 그 사이에 집중국을 어디든 놓게되면 군집에 해당하는 센서들과 집중국의 사이의 최소값은 "군집에 해당하는" 센서들의 거리의 합과 같다.

3. 군집을 생성하게되면 센서들 간의 최대 거리 중 K-1개 만큼 사용하지 않게된다.

4. 2와 3의 조건에 의해 센서들 간의 거리들 중 각 센서들의 최대 거리 K-1 개를 제외하면 우리가 원하는 결과값이 된다.

 

코드

int n,k;
vector<int> sensor;

struct T{
    int idx, size;
};
//각 센서들을 해당 번호와 다음 센서와의 거리를 저장한다

bool cmp(T a, T b){
    return a.size > b.size;
}

void sol(){
	//입력값에 센서들이 무작위로 주어지므로 센서들을 오름차순으로 배치한다
    sort(sensor.begin(), sensor.end());
    
    //센서간의 간격을 저장한다
    vector<T> interval;
    for(int i = 1; i < n; i++){
        T tmp;
        tmp.idx = i-1;
        tmp.size = sensor[i] - sensor[i-1];
        interval.push_back(tmp);
    }
	
   	//간격을 크기를 기준으로 정렬한다
    sort(interval.begin(), interval.end(), cmp);

    int result = 0;
	
    //상위 K-1개를 제외한 거리의 합들이 우리가 구하는 결과값이 된다.
    for(int i = k-1; i < n; i++){
        result += interval[i].size;
    }

    cout << result << endl;
}

 

결론 : 

집중국의 위치에 매료되지 않고 각 센서들이 취할 수 있는 최소 거리에 집중을 해야하는 문제이다.

따라서 군집을 이해하고 가장 큰 거리 사이를 기준으로 군집이 만들어지는 것을 이해해야한다.

 

사용 무기 : sort( )를 할 때 cmp와 같은 함수를 만들어 내가 원하는 형태로 정렬할 줄 알아야 한다. (얻어가야할 내용)

전체 코드

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

int n,k;
vector<int> sensor;

struct T{
    int idx, size;
};

bool cmp(T a, T b){
    return a.size > b.size;
}
void input(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        int s;
        cin >> s;
        sensor.push_back(s);
    }
}

void sol(){
    sort(sensor.begin(), sensor.end());
    vector<T> interval;
    for(int i = 1; i < n; i++){
        T tmp;
        tmp.idx = i-1;
        tmp.size = sensor[i] - sensor[i-1];
        interval.push_back(tmp);
    }

    sort(interval.begin(), interval.end(), cmp);

    int result = 0;

    for(int i = k-1; i < n; i++){
        result += interval[i].size;
    }

    cout << result << endl;
}

int main(){
    input();
    sol();
    return 0;
}