백준 2212번 - 센서(C++)

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

이분탐색인가? 라는 생각이 들 수밖에 없는 문제였다. https://www.acmicpc.net/problem/1477 문제가 떠오르는 문제이기 때문이다. 1477번과 비슷하기도 하다. 만약 2212의 한 커버 거리의 최대나 최소를 구하라고 했다면 1477번 처럼 풀 수 있을 것이다.

 

이 문제는 시뮬레이션처럼 어디에 기지국을 설치할지 정하는 것이 아니라 각 센서 사이의 거리를 구해놓고 가장 먼 사이에다가 설치하면 되기 때문에 전체 값에서 그 값들을 빼주면 되는 문제였다.

 

정렬이던 그리디던 간에 아이디어를 떠올리지 못하면 매우 어려운 문제다.

 

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

int main(){
    vector<int> arr;
    vector<int> gap;

    int n, m; cin >> n >> m;

    for(int i = 0; i < n; i++){
        int tmp; cin >> tmp;

        arr.push_back(tmp);
    }

    sort(arr.begin(), arr.end());

    int answer = 0;

    for(int i = 1; i < n; i++){
        gap.push_back(arr[i] - arr[i - 1]);
        answer += arr[i] - arr[i - 1];
    }

    sort(gap.rbegin(), gap.rend());

    for(int i = 0; i < gap.size(); i++){
        if(i == m - 1) break;
        answer -= gap[i];
        
        
    }

    cout << answer << '\n';
}