[ SWEA 4111 ] 무선 단속 카메라 (C++)

SWExpertAcademy의 무선 단속 카메라(4111 / D4) 문제이다.

[ 문제풀이 ]

1) 처음에 문제를 보고, 어떻게 접근해야 될지 몰라서 굉장히 단순하게 생각나는대로 접근을 했던 것 같다.

   수신 가능 영역의 길이가 가장 짧아지려면, 카메라 간의 거리가 가장 먼 카메라를 따로 수신하게 만들면 될 거라 생각했다.

   극단적인 예시로 아래의 상황을 생각해보자.  

   위의 상황에서, 수신기를 2대를 설치해야 한다. 그럼, 카메라 간의 거리가 가장 먼, 3번 좌표와, 94번 좌표를 포함하지

   않도록, 수신기 2대를 설치하면 될 것이다. 즉, 1 ~ 3번에 수신기 1개, 94 ~ 98 번에 수신기 1개를 설치하면 된다.

   이렇게 생각을 했고, 이렇게 구현을 했더니 PASS를 받을 수 있었다.

   그래서 가장 먼저, 카메라의 좌표들을 정렬을 시켜 주었다. 입력은 정렬순으로 입력되지 않기 때문에, 먼저 정렬을

   시켜 주었다.

   그리고, 해당 카메라들의 거리를 계산한 후, 이 거리들 또한 정렬을 시켜주었다.

   위의 그림으로 예를 들어보자면 다음과 같다.

   카메라의 좌표들을 정렬 = [ 1 , 2 , 3 , 94 , 95 , 96 , 97 , 98 ]

   카메라들 간의 거리를 계산 = [ 1 , 1 , 91 , 1 , 1 , 1 , 1 ]

   카메라들 간의 거리를 정렬 = [ 1 , 1 , 1 , 1 , 1 , 1 , 91 ]

  

   그럼 여기서 한번 생각을 해보자. 수신기가 2대라면, 몇 개의 구간을 뺄 수 있을까 ??

   위에서 말한 '카메라들 간의 거리' 라는 것은 어떻게 보면 구간을 의미한다. 그렇다면 수신기가 2대라면 몇 개의 구간을

   뺄 수 있을까 ?? 더 쉽게 생각해서, 만약 수신기가 1대라면, 몇 개의 구간을 뺄 수 있을까 ?

   수신기가 1대일 경우에는, 무조건 모든 구간을 다 포함해야 한다. 즉, 뺄 수 있는 구간이 0 개이다.

   그렇다면 수신기가 2대일 경우에는 ? 1개의 구간을 뺼 수 있다.

   수신기가 K대 라면 ?? K - 1 개의 구간을 뺄 수 있다.

   즉, '카메라들 간의 거리를 정렬' 한 값들 중에서, K - 1 개의 구간을 빼버리고 나머지 구간을 다 합친 것이 최소길이이다.

   위에서, 수신기가 2대라고 가정했으니, 1개의 구간을 빼버리고 나머지 구간을 다 합쳐보자.

   그럼, 가장 큰 '91'을 빼게 될 것이고, 1을 6번 더해서 '6'이라는 최소 길이가 나오게 된다.

   실제로 위의 그림에서 수신기를 2대를 사용한다면, 1 ~ 3 까지 커버하는 수신기 1대 = 길이 : 2

   94 ~ 98 까지 커버하는 수신기 1대 = 길이 : 4. 총 '6'의 길이가 나오게 된다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
 
#define endl "\n"
#define RANGE 1000010
#define MAX RANGE * 2
using namespace std;
 
int N, K, Answer;
vector<int> Camera, Gap;
 
void Initialize()
{
    Answer = 0;
    Camera.clear();
    Gap.clear();
}
 
void Input()
{
    cin >> N >> K;
    for (int i = 1; i <= N; i++)
    {
        int a; cin >> a;
        a = a + RANGE;
        Camera.push_back(a);
    }
}
 
void Solution()
{
    sort(Camera.begin(), Camera.end());
    for (int i = 1; i < Camera.size(); i++)
    {
        int Diff = Camera[i] - Camera[i - 1];
        Gap.push_back(Diff);
    }
 
    sort(Gap.begin(), Gap.end());
    int Size = Gap.size();
    for(int i = 0 ; i < Size - (K - 1); i++)
    { 
        Answer = Answer + Gap[i];
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}