[그리디] BOJ 2212 센서

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

2212번: 센서

 

문제 해결 알고리즘

 

각 센서간의 차이를 구한 것들을 배열에 넣고 정렬한 후 큰 순서대로 차이들을 K-1개씩 센서 중에 가장 큰 정수거리와 가장 작은 정수거리를 뺀 값에 빼준다. 그 값을 출력한다.

 

소스 코드

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    
    int N, K; cin >> N >> K;
    
    if(N == 1) {
        cout << 0;
        return 0;
    }
    
    vector<int> sensor(N);
    vector<int> dis(N-1);
    for(int i=0;i<N;i++){
        cin >> sensor[i];
    }
    
    sort(sensor.begin(), sensor.end());
    
    int result = sensor[N-1] - sensor[0];

    for(int i=0;i<N-1;i++){
        dis[i] = sensor[i+1] - sensor[i];
    }
    
    sort(dis.begin(), dis.end());
    
    for(int i=N-1;i>=N-K;i--){
        result -= dis[i];
    }
    
    cout << result;
    
}