개요

[링크]백준 2212번: 센서

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

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

접근 방식

• 처음 방식은
  정렬 후 원래 하려던 건 값을 정렬한 후에 index 0부터 비교를 해서 차이가 일정하면 패스하고 차이가 달라지면
  거기에 기지국을 세우고 기지국이 너무많아지면
  다시 비교후 저장된 차이값에 +1만큼해서 기지국 또 세우고 이런식으로 접근했는데
  +1만큼 세웠을때 차이가 불규칙하며 어떻게 비교를 해야할지 몰라서 막혔다.

• 두번째 방식
  정렬을 한후 각값의 차이만큼 또 정렬을 하게된다면
  차이가 적은 값부터 정렬이 될 텐데
  그럼 차이가 제일작은순으로 센서-기지국 값만큼 더해주면 답이된다.
  기지국에서 센서들을 할당을 하는데
  센서들에게 수신을 받는값은 센서-기지국(n-k)이다.
  n-k가 나온 이유는
  센서의 간격은 총 n-1개인데 기지국이 n-1개의 간격을
  k개로 나눴을 때 버려지는 간격이 k-1개이므로
  우리가 사용하는 간격의 갯수는 총 n-1 - (k-1) = n-k이다.

코드

#include<iostream>							//3
#include<vector>							
#include<algorithm>

using namespace std;

vector<int> inputN;										//입력값 받고 정렬할 벡타
vector<int> differ;										//정렬된 값들을 넣고 정렬할 벡터

void input(int& sensors, int& manages) {				//입력값 받는 함수
	int temp=0;
	cin >> sensors >> manages;

	for (int i = 0; i < sensors; i++) {
		cin >> temp;
		inputN.push_back(temp);
	}
}

void solution(int& sensors, int& manages) {				//답 도출 함수
	int ans = 0;
	sort(inputN.begin(),inputN.end());					//들어온 값 정렬
	for (int i = 1; i < inputN.size(); i++) {		
		differ.push_back(inputN[i] - inputN[i - 1]);	//differ 벡터에 정렬된 두 값 차이 다 push
	}
	sort(differ.begin(), differ.end());					//각 차이를 또 정렬한 후
	for (int i = 0; i < sensors - manages; i++) {		//0부터 sensors- manages까지 값을 다 더한것이 답.
		ans += differ[i];
	}

	cout << ans;

}

int main() {
	int sensors = 0, manages = 0;
	input(sensors,manages);
	solution(sensors,manages);
}

문풀후생

정렬되고 그 차이값을 또 정렬하는 기술은 생각하지 못했다. 차이값이 달라지는 곳을 체크할 수 있는 스킬을 배운 것 같다.