백준 Gold 5 센서

센서 (백준 Gold 5)

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

n개의 센서와 k개의 기지국 개수가 주어지고
n개의 센서들의 각 좌표가 주어질 때
기지국으로 관리할 수 있는 최소 영역 범위를 구하는 문제

• 일단 ‘기지국’을 따로 설치하여 비교하는 문제는 아니다
  그러니까 각각의 센서들과 기지국 위치를 비교하여
  그 합이 최소가 되는 것을 구하는 방식은 아님
  (처음에 헷갈린 부분)
  (아마 이러한 방식이였다면, 스택/큐의 사용이 고려되지 않을까?)
  (예제 1이 해당 방식으로 풀어지지 않기에 다른 방법이라 생각)
  

• 요점은 ‘기지국’을 임의의 영역에 설치하였을 때,
  모든 기지국이 ‘감당’하는 길이들을 줄이는 것
  

풀이 방법

사실 처음에는 감이 잘 안왔지만
요점은 생각보다 간단하였다

• 각 정점 간의 ‘길이’가 중요
  

따라서 먼저 각 좌표들을 ‘정렬’하고
각 좌표들의 ‘거리’를 모은 후
다시 그 거리들을 정렬시키면 쉽게 풀 수 있는 문제이다

• 각각의 거리들 중, k-1개 만큼 ‘무거운 거리’를 제거
  (k가 1인 경우는 모든 거리를 담당해야 하기에 -1)
  

• k가 2개부터는 특정한 ‘거리’의 반대 방향에 기지국을 설치 가능
  

k = 2 인 경우
a - b  c - d

b c 거리가 제일 길다면
-> a-b 거리와 c-d 거리만 구할 수 있음

반대로 a b 거리가 제일 길다면

a b-c-d

이런식으로 기지국을 설치 가능

따라서 기지국을 설치하는 위치는 딱히 상관없고
기지국 k-1개 당, ‘긴 거리’를 제거해 나가면 풀 수 있는 문제

제출 코드

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

using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;

	vector<int> cod(n),lenVec;
	for (int i = 0; i < n; i++)
	{
		cin >> cod[i];
	}

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

	for (int i = 1; i < n; i++)
	{
		lenVec.push_back(cod[i] - cod[i - 1]);
	}

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

	int fullLen = cod.back() - cod[0];
	for (int i = 0; i < k - 1; i++)
	{
		if (lenVec.empty())
			break;
		fullLen -= lenVec.back();
		lenVec.pop_back();
	}

	cout << fullLen;

	return 0;
}

결과

if(lenVec.empty())

런타임 에러는 해당 코드를 빼먹고 돌려서 발생하였다
이후 넣어주어 통과할 수 있었다
(k가 n개 보다 많이 들어올 수 있는 점을 간과하였다)