백준 2212번 [센서](C++) -yes6686- 티스토리

백준 문제 풀이: 2212 [센서]

---

문제 링크: https://www.acmicpc.net/problem/2212

문제 설명:

각 센서는 일직선 상에 위치하고 있으며, 이 센서들을 K개의 기지국으로 커버하려고 합니다. 기지국은 특정 위치를 커버할 수 있으며, 기지국 간의 최소 거리 합을 줄이는 것이 목표입니다.

즉, 센서를 K개의 구역으로 나누었을 때, 각 구역 내 센서 간의 거리 합이 최소가 되도록 하는 문제입니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int arr[10001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    // 센서 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 센서가 k개 이상이면 모든 센서에 기지국을 두어야 하므로 거리합은 0
    if (n <= k) {
        cout << 0 << '\n';
        return 0;
    }

    // 센서 위치 정렬
    sort(arr, arr + n);

    // 센서 간 거리 차이 계산
    vector<int> gaps;
    for (int i = 0; i < n - 1; i++) {
        gaps.push_back(arr[i + 1] - arr[i]);
    }

    // 거리 차이 내림차순 정렬
    sort(gaps.rbegin(), gaps.rend());

    // 가장 긴 k-1개의 구간을 없애고 나머지 합산
    int ans = 0;
    for (int i = k - 1; i < gaps.size(); i++) {
        ans += gaps[i];
    }

    cout << ans << '\n';
    return 0;
}

예제 입력:

6
2
1 6 9 3 6 7

예제 출력:

5

---

코드 설명

• 핵심 알고리즘: 센서 간 거리 차이를 정렬하여 가장 긴 k-1개의 구간을 없애고, 나머지 거리 합을 구합니다.
• 구현 세부사항:
  • 센서가 k개 이상이면 거리 합은 0이므로 예외 처리를 수행합니다.
  • 센서를 정렬한 후 인접한 센서 간의 거리 차이를 구합니다.
  • 이 거리 차이를 내림차순으로 정렬한 후, k-1개의 가장 큰 값을 제외하고 나머지 거리 합을 구합니다.
• 시간 복잡도: O(N log N), 거리 정렬이 주된 연산

---

결과

입력된 센서 위치를 최적으로 그룹화하여 최소한의 거리 합을 정확히 계산합니다. 정렬과 그리디 알고리즘을 활용한 최적화 문제를 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!