[백준/Baekjoon] 2212 센서 C++ :: Greedy

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

2212번: 센서

---

1. Logic

- 집중국의 수신 가능 영역을 최소화 시키기 위해서는 집중국을 세울수 있는 갯수로 지어진 k만큼 다 세워 줘야 한다.

 

센서를 세우는데 가장 적합한 위치는 오름차순 정렬을 했을 때 인접한 두 센서의 가운데에 세워야 한다. 

케이스에서 나온 

1 6 9 3 6 7 > 오름차순 정렬

1 3 6 6 7 9 > 인접한 두 노드의 거리를 빼주기

dist : 2 3 0 1 2 > 또 오름차순 정렬

0 1 2 2 3  > 가장 짧은 거리 ->  범위 - 구간을 한 갯수만큼 더해줌

 

그림으로 보자면

 

검은 선은 센서의 위치이고 빨간색이 집중국이 미치는 범위이다. 항상 

1번 그래프를 보면 1~6까지 집중국이 담당하는데 실제로 3~6은 사이에 노드가 없기때문에 단지 6하나 만으로 집중국 하나가 3을 낭비하여 사용하고 있는 것이다.

2번 그래프를 보면 1번 그래프와 같이 3만큼을 낭비하여 사용하고 있는 모습이다.

정답인 3번 그래프를 보면 1~3번 센서까지는 첫번째 집중국 하나가 나머지 센서들은 남은 집중국 하나가 마크하여 관리한다. 

 

일반화 시켜보면 우리는 각 범위를 오름차순 정렬하여 범위가 작은거부터 n - k개를 더해줘야 한다.

센서 간의 거리의 범위 : n - 1

집중국을 세웠을 때 제외되는 범위(빨간색 그래프의 연결되지 않는 부분) : k - 1

==> n-1 -(k-1) = n+k

그래서 마지막에 for문을 n+k까지 돌며 범위의 최솟값을 더해주는 것이다.

 

센서가 노드 갯수보다 적다면 집중국 한개가 최대한 적은 범위로 묶여 동작해야함.

---

2. Code

#include<bits/stdc++.h>

using namespace std;

vector<int> sensor;
vector<int> dist;

int main() {
    int answer = 0;
    int n, k;
    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        sensor.push_back(a);
    }

    sort(sensor.begin(), sensor.end());

    for(int i = 0; i < n - 1; i++) {
        dist.push_back(sensor[i + 1] - sensor[i]);
    }

    sort(dist.begin(), dist.end());

    for(int i = 0; i < n - k; i++) {
        answer += dist[i];
    }

    cout << answer;
}

---

3. Feedback

C++언어보다 한국어 공부를 조금 더 해야할 것 같다,,,ㅋㅋㅋㅋㅋㅋ 문제 이해를 하는데 시간을 엄청 썼다.

항상 느끼는 거지만 그리디 문제는 구현력에 상관없이 아이디어 싸움인 것 같다. 문제를 빠르게 이해하고 문제에 맞는 아이디어를 떠올리기가 중요!

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐