4111. 무선 단속 카메라

4111. 무선 단속 카메라

거리의 모든 합은 결국 정해져 있기 때문에, 가장 큰 값부터 없애나가면 된다고 생각했다.

즉 예제에서 1-3-6-7-9 에 카메라가 있다면, 그 사이의 거리는 2-3-1-2 가 된다. 

이때 k값이 2라면, 2 3 1 2 중에서 3만을 제거하면 구간이 두개가 되고 2 , 1-2 가 되어 합 5가 정답이 된다.

이런식으로 정렬해서 k의 값에 따라 가장 큰 값을 차례로 제거해주면 된다.

따라서

1. 카메라가 있는 곳의 위치를 파악한다.

2. 중복 계산을 피하기 위해 다시 카메라의 위치를 통합하여 v 벡터에 담는다.

3. v벡터를 이용해서 카메라 사이의 거리 값을 모두 diff 벡터에 담는다.

4.diff를 정렬하여 k값에 따라 앞에서부터 더해간다

//배운점

처음에 size선언을 하지 않고, diff.size()-(k-1) 을 그대로 사용했는데 segment 에러가 발생했다.

그래서 물어보니 size()함수는 unsigned int 형이라서 음수가 되면 언더플로우가 발생하기 때문이었다.

warning 을 평상시에 간과했는데, warning에 뜨는 문제였다. size()함수에 대한

warning 을 항상 무시하는 습관이 있었는데, 문제가 없다는 걸 확신할 때만 넘어갈 수 있어야한다!

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
#include<string.h>
using namespace std;
int camera[2000002] = { 0, };
vector<int> v;
vector<int> diff;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
    
        int n, k, ans = 0;
        memset(camera, 0, sizeof(camera));
        v.clear();
        diff.clear();
        cin >> n >> k;
 
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            camera[tmp+1000000] = 1;
        }
 
        for (int i = 0; i < 2000002; i++)
        {
            if (camera[i]==1)
            {
                v.push_back(i);
            }
        }
 
        sort(v.begin(), v.end());
 
        for (int i = 1; i < v.size(); i++)
        {
            int x = v[i] - v[i - 1];
            diff.push_back(x);
        }
 
        sort(diff.begin(), diff.end());
        int size = diff.size();
 
        for (int i = 0; i < size - (k - 1); i++)
        {
            ans += diff[i];
        }
 
        cout << "#" << t << " " << ans << "\n";
 
    }
    return 0;
}