[백준 2212] 센서, C++

이 문제는 단순 구현 문제이다. 근데 일단 문제를 이해하는데 꽤나 머리가 아팠다.

 

 

입력 예제 1번을 가지고 설명을 한다면

 

 

 

위처럼 점들 사이의 거리를 계산을 해서 가장 짧은 집중국 거리를 구하는 방법을 것이다. 그래서 첫번째 집중국의 거리 2와 두번째 3을 더해서 답이 5가 나온다.

 

문제를 간단하게 생각하는 방법이 있다. 일단 집중국의 개수는 K개일테니 그러면 일렬로 나열되어있는 분에서 가장 긴거리 부분을 K - 1번 지운다고 생각하면 된다. 예를 들어서

 

위처럼 센서 사이의 모든 거리를 나타내고 하지만 우리는 K개의 집중국을 만들어야하고 그러면 가장 긴 거리 애들을 K - 1번 제거하면 총 K개의 집중국이 남게 되는것이다. 

 

그러면 다시 순서를 나타내면

 

1. 센서의 위치들을 담고 오름차순 정렬한다.
2 센서들 사이의 거리를 나타내는 배열을 다시만들고 오름 차순으로 정렬한다.
3. 가장 긴 거리 K - 1을 제외한 나머지 길이들을 다 더하면 그게 답이다. 

 

// 2212
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int main(){
  int N,K,V;
  cin >> N >> K;
  vector<int> arr;
  for (int i = 0; i < N; i++){
    cin >> V;
    arr.push_back(V);
  }

  sort(arr.begin(), arr.end());
  vector<int> diss;
  for (int i = 0; i < N - 1; i++){
    diss.push_back(arr[i + 1] - arr[i]);
  }

  sort(diss.begin(), diss.end(), [](const auto &a, const auto &b){
    return a > b;
  });
  int answer = 0;
  for (int i = 0; i < diss.size(); i++){
    if (i < K - 1)
      continue;
    else
      answer += diss[i];
  }
  cout << answer << endl;
  return 0;
}