[C++] 백준 온라인 저지 2212번 센서 풀이

도로 위에 세워진 집중국들의 수신 영역 길이의 최소합을 구하는 문제

 

---

문제

 

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

 

입력

첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.

 

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

 

 

풀이

 

 역시 문제를 처음 봤을 땐 무슨 소리인가 싶었지만... 질문 게시판 보니까 (다행히)저처럼 이해 못 한 분들이 계셨어서 해설을 참고할 수 있었습니다. 예제 1번을 1 3 6 6 7 9 로 정렬한 다음 [1, 3] [6, 9] 구간으로 묶은 후 각 구간의 거리는 2와 3입니다. 2+3 = 5 가 되어서 예제 1번 정답이 5 라고 하더라고요... 

 여기서 주어진 입력을 오름차순으로 정렬한 다음 K개만큼 묶었을 때 각 구간 내의 거리가 최소가 되어야 한다는 것을 알 수 있었습니다. 

 

 그럼 문제는 이해했는데 답을 구하는 과정을 어떻게 구현하나?

.

.

.

 임의로 K개만큼 묶어보는 건 너무 비효율적일 거 같은데... 안타깝게도 이 부분에 대한 풀이가 떠오르지 않아 구글링을 했습니다.

 

https://joodaram.tistory.com/63

[백준 2212] 센서_greedy(C++)

참고 블로그

 

 

 문제의 포인트는 수신국의 위치를 어디로 정하느냐가 아니었습니다. 따흑

 역시 그리디는 보이는대로 푸는 것이 아니었음을...

 

arr[0]	arr[1]	arr[2]	arr[3]	arr[4]	arr[5]
1	3	6	6	7	9

 

 예제 1번을 정렬하면 위와 같이 됩니다. 

 우리가 구해야 하는 것은 집중국의 수신 가능 영역의 최소합을 구하는 것인데 합이 최소가 되려면 각 센서간 구간 거리가 최소가 되어야 한다는 말과도 같습니다. 그러면 위 배열에서 각각 앞뒤로 위치한 센서들의 거리만 구해주면 됩니다. 

 arr[0]-arr[1] / arr[1]-arr[2] / arr[2]-arr[3] / arr[3]-arr[4] / arr[4]-arr[5] 

 얘네의 거리만 구해주면 되죠. arr[0]-arr[2]와 같은 것은 오름차순으로 정렬되어 있는 상황에서 어차피 최소값이 될 수 없기 때문에 구할 필요가 없습니다. 

 

arr[0]-arr[1]	arr[1]-arr[2]	arr[2]-arr[3]	arr[3]-arr[4]	arr[4]-arr[5]
2	3	0	1	2

 

 앞뒤로 위치한 센서간 거리를 구하면 위와 같습니다. 

 

0

1

2

2

3

 

 이것을 정렬하면 위와 같이 됩니다. 

 그런데 문제에서 집중국의 개수가 K개로 정해져 있기 때문에 거리들 중 가장 긴 것부터 K - 1개를 제거해준 뒤 나머지를 더하면 됩니다. 

 이렇게 되는 이유는 만약 집중국이 1개라면 최소 거리가 8이지만 (1 ~ 9 까지의 거리)

 집중국이 하나 더 생기면 센서 사이의 거리 중 가장 먼 부분을 잘라서 두 개의 집중국이 관리하게 하면 됩니다. 

 

https://excited-hyun.tistory.com/70

[백준 2212 - C++] 센서 : 그리디 알고리즘

자세한 그림과 설명은 이 블로그 참조

 

 즉 센서 사이의 거리 중 가장 먼 거리를 집중국 개수-1 만큼 제외한 거리들을 더하면 답이 되는 것이죵...! 

 

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N, K;
    cin >> N >> K;
    
    vector<int> positions(N, 0);
    for (int i = 0; N > i; i++)
    {
        cin >> positions[i];
    }
    
    //센서 위치 오름차순 정렬
    sort(positions.begin(), positions.end());
    
    vector<int> distances; //센서 간 거리를 저장할 벡터
    for (int i = 1; positions.size() > i; i++)
    {
        int dist = positions[i] - positions[i-1];
        distances.emplace_back(dist); //앞뒤 센서간 거리 구하기
    }
    
    //센서간 거리 오름차순 정렬
    sort(distances.begin(), distances.end());
    
    int count = N - K; //최소 거리 개수
    int answer = 0;
    for (int i = 0; count > i; i++)
    {
        answer += distances[i];
    }
    
    cout << answer;
    
    return 0;
}