백준 2212 - 센서

문제

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

2212번: 센서

 

풀이

K개의 집중국을 K개의 직선으로 바꿔서 생각하면 쉽게 해결이 가능한 문제이다. 수신 가능영역 거리의 최소는 센서 사이 직선의 최소 길이로 바꿔 생각하면 된다.

 

N개의 센서들을 정렬하고 인접한 센서 사이의 거리를 구하고 다시 정렬하여 큰 거부터 K - 1개 제거해주면 된다. 예제

 1 6 9 3 6 7의 경우 1 3 6 6 7 9로 정렬이 되고 인접한 거리는 다시 2 3 0 1 2가 된다. 여기서 가장 길이가 긴 직선인 3을 제거하면, 두개의 기지국 중에서 한 개의 기지국은 2만큼 수신하고 나머지 한 개의 기지국 0+1+2 만큼 수신하면 된다. 따라서 길이가 가장 긴 거리부터 삭제하면 최소의 거리를 구할 수 있다.

 

 

코드

#include <iostream>
#include <algorithm>
using namespace std;
 
int sensor[10000];
int dist[999];
int result;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    int N, K;
    cin >> N >> K;
 
    for (int i = 0; i < N; i++)
        cin >> sensor[i];
 
    sort(sensor, sensor + N);
 
    // 인접한 센서 사이의 거리
    for (int i = 0; i < N - 1; i++)
        dist[i] = sensor[i + 1] - sensor[i];
 
    // 거리 내림차순 정렬
    sort(dist, dist + (N - 1), greater<int>());
 
    // 거리가 먼 순서대로 삭제
    for (int i = 0; i < K - 1; i++) dist[i] = 0;
 
    for (int i = 0; i < N - 1; i++) result += dist[i];
 
    cout << result;
 
    return 0;
}