BOJ 2212 - 센서 링크
(2023.09.04 기준 G5)

문제

평면상의 직선으로 표현되는 고속도로 위에 N개의 센서가 있다. 고속도로 위에 최대 K개의 집중국을 세우려고 하는데, 각 집중국의 센서의 수신 가능 영역을 조절하여 모든 센서가 최소 하나의 집중국과는 통신이 가능하게 해야 한다.

집중국의 수신 가능 영역의 길이의 합의 최솟값 출력

알고리즘

정렬 후에 그리디적으로 접근

풀이

만약 위 그림처럼 5개의 센서와 2개의 집중국이 있다면, 위 그림처럼 집중국의 센서의 수신 가능 영역을 조절해야 길이의 합이 최소가 된다.

가장 왼쪽과 오른쪽에 위치해 있는 점끼리 잇는 선분이 곧 모든 점을 포함하는 최소 선분이 되는데, K-1개 만큼 구간을 덜어낼 수 있는 것이다. 가장 길이가 긴 구간부터 덜어내야 길이의 합이 최소가 됨은 자명하므로, 인접한 두 점 사이의 거리를 구해 내림차순으로 정렬하여 min(K-1,N-1)개만큼 전체 선분의 길이에서 빼주자.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, K; cin >> N >> K;
    vector<int> P(N); for (int i = 0; i < N; i++) cin >> P[i];
    sort(P.begin(), P.end()); // 좌표 순으로 정렬

    // 집중국의 개수는 곧 평면상의 점(센서)들을 포함하는 선분의 개수
    // 즉, 점 사이의 거리가 먼 것부터 잇지 않으면 된다.
    vector<int> D; for (int i = 0; i < N - 1; i++) D.push_back(P[i + 1] - P[i]);
    sort(D.begin(), D.end(), greater<int>()); // 인접한 점 사이의 거리를 구해 내림차순으로 정렬
    int result = P[N - 1] - P[0]; // 모든 점을 포함하는 선분의 길이
    for (int i = 0, j = min(K - 1, N - 1); i < j; i++) // (선분의 개수 - 1)개의 거리를 뺀다.
        result -= D[i];

    cout << result;
}

• Python

import sys; input = sys.stdin.readline

N = int(input())
K = int(input())
P = sorted(map(int, input().split())) # 좌표 순으로 정렬

# 집중국의 개수는 곧 평면상의 점(센서)들을 포함하는 선분의 개수
# 즉, 점 사이의 거리가 먼 것부터 잇지 않으면 된다.
D = sorted([P[i + 1] - P[i] for i in range(N - 1)], reverse = True) # 인접한 점 사이의 거리를 구해 내림차순으로 정렬
result = P[-1] - P[0] # 모든 점을 포함하는 선분의 길이
for i in range(min(K - 1, N - 1)): # (선분의 개수 - 1)개의 거리를 뺀다.
    result -= D[i]

print(result)