BOJ 2212 - 센서

www.acmicpc.net/problem/2212

2212번: 센서

 

이 문제는 그리디로 푸는 문제로, 

처음에 각 센서들의 좌표를 입력 받아서 오름차순 정렬하고 (일직선 상에 분포하므로 편의상 오름차순 정렬)

전체 센서의 거리를 계산하고, 각 센서별 거리를 담아둔다.

그리고 각 센서별 거리를 내림 차순 정렬한뒤,

전체 거리 리스트에서 뒤에서 k 개만 남겨두고, 앞에 남은것들 (즉, 거리가 큰 놈들) 을 전체거리값에 빼면 결국엔 k 개의 집중국이 갖는 값은 최소값이 된다.

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int n, k; // 센서 수, 집중국 갯수 
vector<int> vec, distList; // 센서 좌표 리스트,  센서 간 거리 리스트 
 
bool comp(int& a, int& b) {
    return a > b;
}
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> n >> k;
    if (k >= n) { // 집중국이 센서 갯수보다 많은경우 예외처리 
        cout << "0";
        return 0;
    }
    
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        vec.push_back(num);
    }
    
    sort(vec.begin(), vec.end()); // 센서를 오름 차순 정렬 (일직선 상에 연결되어 있으므로) 
    
    int total = vec[n - 1] - vec[0]; // 전체 거리 
    
    for (int i = 0; i < n - 1; ++i) 
        distList.push_back(vec[i + 1] - vec[i]); // 각 센서별 거리 담기 
        
    sort(distList.begin(), distList.end(), comp); // 각 센서별 거리 내림차순 정렬 
    
    for (int i = 0; i < k - 1; ++i) // k 개의 집중국 수신 가능 영역 계산 
        total -= distList[i];
        
    cout << total;
    
    return 0;
}