[Algorithm/C++17] 백준 2212 센서

문제

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

2212번: 센서

풀이 방법

센서를 점으로 보면 다음과 같이 해석된다.

일직선상에 N개의 점이 있을 때 이들을 다 포함하는 길이의 합이 최소가 되는 K개의 선분을 만든다.

선분 사이의 K-1개의 공간이 생기게 되는데, 이 공간들을 가장 크게하면 선분 길이 합이 최소가 된다.

1. 점들을 오름차순으로 정렬한다.
2. 인접한 점들 간 거리(선분 길이)를 내림차순으로 정렬한다.
3. 인접한 점들 간 거리를 모두 합한다.
4. 합한 값에서 가장 긴 거리부터 k-1번 빼준다.
5. 계산 결과 값은  남아 있는 K개의 선분 길이이다.

다시 말해, 선분 길이를 다 더한 뒤 가장 긴 선분부터 k-1번 빼준다고 보면 된다. 

그렇게 하면 남아있는 k개의 선분의 길이의 합은 최소가 된다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
int main()
{
    int n, k, t;
    scanf("%d\n%d", &n, &k);
    vector<int> v;
    for(int i=0; i<n; i++)
    {
        scanf("%d", &t);
        v.push_back(t);
    }
    // 집중국이 센서보다 많으면 선분이 필요없으므로 최소 길이는 0
    if(k >= n)
    {
        printf("0");
        return 0;
    }
    // 점들을 오름차순 정렬한다.
    sort(v.begin(), v.end());
    vector<int> diff;
    int sum = 0;
    // 인접한 점들 간 거리를 계산한다.
    // 계산된 거리를 합한다.
    for(int i=0; i<n-1; i++)
    {
        diff.push_back(v[i+1]-v[i]);
        sum += diff[i];
    }
    // 인접한 점들 간 거리를 내림차순 정렬한다.
    sort(diff.begin(), diff.end(), greater<int>());
    // 가장 긴 거리부터 k-1번 빼준다.
    for(int i=0; i<k-1; i++)
    {
        sum -= diff[i];
    }
    printf("%d", sum);
    return 0;
}

고찰

처음에는 문제 이해를 못해서 예제 입력을 그림판에 그려보았다. 쉬운 문제는 무작정 큰 값이나 작은 값을 골라 계산하는 문제였는데, 그리디 초보인 나는 한번 더 생각해봐야했던 문제다.