[99클럽/코딩테스트 챌린지/C++] 집중국 설치 문제 해결 과정

문제 링크 : 

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

 

문제 요약

한국도로공사는 고속도로에 설치된 N개의 센서가 수집한 데이터를 분석하기 위해 K개의 집중국을 세우려고 합니다. 각 집중국은 일정 구간을 커버할 수 있으며, 모든 센서가 최소 하나의 집중국과 통신할 수 있어야 합니다. 집중국의 수신 영역 길이의 합을 최소화하는 것이 목표입니다.

이 문제는 센서들이 특정 위치에 고정되어 있고 집중국의 수신 구간 길이를 최소화하면서 모든 센서들을 커버해야 하는 상황을 다룹니다.

접근법

1, 센서 위치 정렬: 센서 위치를 오름차순으로 정렬하면 인접한 센서 간의 거리를 쉽게 계산할 수 있습니다.

2, 센서 간 거리 계산: 정렬된 센서 간의 거리를 계산하여 각 인접한 센서들 사이의 거리를 구해 리스트로 저장합니다.

3, 큰 거리 제거로 그룹 나누기:

• 최대 KKK개의 집중국을 설치할 수 있으므로 센서를 최대 KKK개의 그룹으로 나눌 수 있습니다.
• 거리 리스트에서 가장 큰 (K-1)개의 거리를 제거하여 KKK개의 그룹을 만듭니다. 이렇게 하면 나머지 센서 간 거리의 합이 최소화됩니다.

4, 거리 합산: (K-1)개의 큰 거리를 제거한 후 남은 거리들의 합을 구하면 집중국 수신 영역의 길이 합의 최솟값을 구할 수 있습니다.

5, 예외 처리: 예외 상황으로는 K ≥ N인 경우를 고려해야 합니다. 집중국의 개수가 센서 개수보다 많거나 같다면, 각 센서마다 하나의 집중국을 배치할 수 있으므로 모든 센서가 커버됩니다. 이 경우, 수신 거리의 합은 0이 됩니다.

전체 코드

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

using namespace std;
int N = 0;
int K = 0;
vector<int> sensers;
int main() {

	std::cin >> N;  // 반복 횟수 N 입력 받기
	std::cin >> K;
	if(N <= K)
	{
		std::cout << 0 << '\n';
		return 0;
	}
	sensers = vector<int>(N);
	for(int i = 0; i < N; i++)
	{
		std::cin >> sensers[i];
	}

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

	vector<int> dists = vector<int>(N - 1);
	for(int i = 1; i < N; i++)
	{
		dists[i - 1] = sensers[i] - sensers[i - 1];
	}

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

	for(int i = 0; i < K - 1; i++)
	{
		dists.pop_back();
	}

	int answer = 0;
	for (int dist : dists)
	{
		answer += dist;
	}

	std::cout << answer << '\n';
	return 0;
}

배운 점

• 정렬과 그룹화: 문제를 해결할 때, 정렬을 통해 인접한 요소 간의 차이를 계산하고 큰 값을 제거하는 방식으로 그룹을 나누어 최적의 해법을 도출하는 방법을 배웠습니다. 이 접근 방식은 집중국의 수신 영역 길이 합을 최소화하는 데 유효했습니다.
• 예외 처리의 중요성: 문제 풀이 과정에서 예외 처리가 매우 중요하다는 것을 다시 확인했습니다. 특히 K >= N과 같은 경우에 대한 예외 처리가 부족할 경우 런타임 에러가 발생할 수 있음을 깨달았습니다.
• 큰 거리 제거를 통한 최적화: 센서를 그룹으로 나누는 과정에서 큰 거리를 제거하는 방식이 효과적이라는 점을 배웠습니다. 큰 거리를 제거함으로써 각 그룹 내의 거리를 최소화할 수 있어, 집중국의 수신 가능 영역 길이 합을 최소화하는 데 도움이 되었습니다.

결론

이 문제를 통해 정렬과 인접 요소 간의 차이를 활용해 최적의 그룹을 나누는 전략을 익힐 수 있었습니다. 최적화 문제에서 거리의 합을 최소화하는 데 큰 값들을 제거하는 방식이 유효하며, 이를 통해 간단한 방식으로 최적의 해법에 접근할 수 있었습니다.

또한, 예외 상황을 정확히 처리해야만 안정적인 프로그램을 작성할 수 있다는 점에서 예외 처리의 중요성을 다시 확인하게 되었습니다.