백준(C++) 2212번 [센서]

2212번 센서

접근방법

그리디 알고리즘 보강 추천 문제 중 하나이다. 문제 요약하면 1차원 고속도로 위에 센서가 원점을 기준으로 위치별로 N개가 있는데 이 센서를 기지국에 다 포함시켜야한다. 기지국의 개수는 K개이다. 즉, 센서를 K개의 그룹으로 나눈뒤 나눈 그룹중 최소 거리의 합을 출력하면된다.

쉽게 쉽게 단계를 나눠 보았다.

1. N개 센서 입력

2. N개의 센서 정렬

3. 정렬된 센서들 사이의 거리를 다른 컨테이너에 저장(N ,N+1)

4. 컨테이너를 내림차순으로 정렬 그 후 센서들의 최대 거리의 합을 저장

5. K-1(K가 1이면 돌 필요가 없음)번 센서들 끼리의 거리가 큰 순서로 최대 거리의 합에 빼기 연산

6. 연산값을 출력

 

순으로 진행 하였다.  

 

처음 딱 코드를 한후 테스트 케이스를 확인 한후 제출을 해봤는데 Out of Bound 오류가 나왔다.

그 이유는 기지국이 센서의 개수와 같거나 큰 경우가 있었기 때문이다. 그러면 거리가 0이 나온다.

어려운 경우의 수만 생각을 해보니 예외 수 같은 것을 배제하지 못했다.

19~23 의 코드를 추가한 후 정답을 얻었다.

 

코드는 다음과 같다  

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N,K;
    cin >> N >> K;
    vector<ll> sensor(N);
    for(int a=0;a<N;a++)
    {
        cin >> sensor[a];
    }
        
    if(K >= N)
    {
        cout << 0 << "\n";
        return 0;
    }
    sort(sensor.begin(),sensor.end());
    vector<ll> dis;
    dis.reserve(N-1);
    for(int a=0;a<N-1;a++)
    {
        dis.push_back(sensor[a+1] - sensor[a]); //reserve 후 push_back 하면 입력시 조금 최적화가 되지만 그냥 위에처럼 고정 위치 선언후 입력 가능
    }

    sort(dis.begin(),dis.end(),greater<ll>());

    ll total = sensor[N-1] -sensor[0];

    for(int a=0;a<K-1;a++)
    {
        total -= dis[a];
    }

    cout << total << '\n';

    return 0;
}