이번 문제는 백준의 2212번 문제 센서 문제이다.
문제를 먼저 차근차근 한 번 읽어보자.
사실 처음 문제를 읽었을 땐 도저히 이해가 잘 안됐다.
그래서 질문 게시판을 참고하며 문제를 꾸역꾸역 이해했다.
기존에 설치된 센서에 대해서, 집중국을 설치해야 한다.
단, 집중국에서 수집하려면 모든 센서와 연결이 되어있어야 한다.
이 때 집중국이 수집 가능한 거리의 합이 최소가 되게 해야 한다.
그 말은, 아래와 같이 해석할 수 있다.
집중국의 수만큼 구간이 정해지는데, 구간의 길이의 합이 최소가 되게 해라.
단 각 구간의 모든 센서와 집중국은 연속되는 번호여야 한다.
문제를 어떻게 해결할 수 있을까?
그리디
문제를 보았을 때, 집중국의 위치를 내가 직접 고를 수 있기 때문에
집중국을 모두 놓아보는 방식을 먼저 생각해보았다.
하지만 센서가 최대 10000개이고, 집중국은 최대 1000개이기 때문에
모두 놓아보는 백트래킹(완전 탐색) 방식은 시간초과가 발생할 것이다.
따라서 직접 선택을 하지만, 연산 수가 적은 그리디 문제일 것 같다.
항상 거리의 합이 최소가 되는 집중국의 위치를 고르며 나아가보자.
어떤 위치를 골라야 구간의 합이 최소가 될 수 있을까?
구간 벡터의 이용
먼저 떠오른 생각은, 따로 벡터를 선언하여 구간의 길이를 저장하는 것이다.
기존의 센서가 설치된 위치 벡터를 만든 다음 오름차순 정렬을 한다.
앞에서부터 구간의 길이를 모두 새로운 벡터에 저장하도록 한다.
이후, 구간 벡터를 한 번 더 정렬하여 앞에서 부터 기지국 수 만큼 고른다.
꽤 그럴싸한 풀이인 것 같다.
그런데, 위치 벡터의 모든 구간을 저장하면 문제가 생긴다.
예를 들어 1 6 9 3 6 7라고 위치들이 주어졌다고 생각해보자.
1 3 3 6 6 7 7 9 들이 저장될 것인데,
앞에서 부터 뽑는다면 1 3 6 7 만 뽑히게 될 것이다.
이는 문제가 원하는 의도에 맞지 않는 방식이다.
모든 센서가 수집가능해지는 기지국의 수집 구간을 구해야 하기 때문이다.
예시에 나오는 해당 문제의 정답은 1 3 6 7 8 9 구간인데,
어떻게 해야 해당 구간을 연결시켜 구할 수 있을까?
반대로 생각할 것
사실 가장 최소가 되는 구간부터 뽑는게 아니다.
반대로 한 번 생각해보자.
만약 1 6 9 3 6 7이라고 위치가 주어지고, 기지국이 하나라면?
8이라는 전체 구간을 기지국 하나로 모두 수집해야 한다는 말이다.
위에서 잘랐던 구간을 모두 더했을 때, 8이라는 길이가 나옴을 알 수 있다.
하지만 이 때 기지국 하나를 추가해서 구간을 줄이려고 한다면?
가장 긴 3 6 구간을 잘라내서 1 3 6 9로 분배할 수 있다.
의미는 없지만 기지국을 하나 더 추가해서 3개로 운용한다면?
다음으로 긴 7 9 구간을 잘라내서 6 7 9로 분배할 수 있다.
즉, 우리는 긴 구간부터 기지국의 수 - 1 개를 덜어내면 된다!
구현 코드는 아래와 같다.
cin >> sensor_num >> centre_num;
for (int i = 0; i < sensor_num; i++) {
cin >> sensor_pos;
coord_list.push_back(sensor_pos);
}
// centre_num개의 구간으로 분할해야 한다.
// 하지만, 각 구간의 길이의 합이 최소여야 한다.
sort(coord_list.begin(), coord_list.end());
// 우선 각 구간의 길이를 저장하기 위해, 정렬한다.
for (int i = 1; i < coord_list.size(); i++)
dist_list.push_back(coord_list[i] - coord_list[i - 1]);
// 앞에서 뒤로 모든 구간의 길이가 저장된다.
sort(dist_list.begin(), dist_list.end());
// 구간들 또한 오름차순 정렬을 해야 한다.
for (int i = 0; i < sensor_num - centre_num; i++)
answer += dist_list[i];
// 구간 덜어내기
cout << answer;