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

[문제]

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

2212번: 센서

• 도로위에 N개의 센서를 설치.
• 센서들이 모은 정보를 기반으로 고속도로위에 최대 k개의 집중국을 세움
  • 조건2.각 집중국의 수신가능 영역의 길이합을 최소화
  • 1.N개의 센서가 적어도 하나의 집중국과는 통신을 해야함(꼭 하나가 연결)
  • 출력
  • 각 집중국의 수신가능영역의 거리 합의 min값

 

[문제 풀이]

어디를 수신국으로 정할것이냐가 관건이라고 생각했다

첫번째 수신국이 집중국일때, 두번째가 집중국일때 .... 이렇게 다 해봐야 하는건가 싶어서 생각해봤는데

만약 그렇게 되면 집중국이 두개면 두개의 조합을 다 구해야되는데 이렇게 되면 시간초과 걸릴것같았다(=백트래킹)

생각해보니 애초에 그럴필요가 없었다..(꾸준함님 블로그를 참고했습니다 -> https://jaimemin.tistory.com/1323)

정해진 집중국 중에서 나와 거리가 적은 집중국으로 부터 수신을 받아야 min값이 나오기때문에 센서들의 위치를 우선 정렬시켜준 뒤(예제로 보자면)

s[1]	s[2]	s[3]	s[4]	s[5]	s[6]
1	6	9	3	6	7

순서가 뒤죽박죽이니까 정렬하면

s[1]	s[4]	s[2]	s[5]	s[6]	s[3]
1	3	6	6	7	9

이렇게 된다

수신국을 어디로 정하냐? ← 가 포인트가 아니였단말....ㅠㅠ

어차피 우리가 구해야되는건 각각의 수신가능영역의 최소거리값들의 합이 되어야 전체값도 min 이 되므로

s[4] - s[1] / s[2] - s[4]/ s[5] - s[2] / s[6] - s[5] /s[3] - s[6] 의 차이만 서로 비교해주면 되는 것이다!

** s[2]-[s1]와 같이 term이 2이상 나는 기지국간의 차이는 왜 비교를 안하냐면, 이들은 어차피 비교대상이 못된다 최소값이 되지 못하기때문이다

위의 차이들의 값은

s[4] - s[1]	s[2] - s[4]	s[5] - s[2]	s[6] - s[5]	s[3] - s[6]
2	3	0	1	2

이다.

이것들을 또 정렬을하면 → 0 1 2 2 3 인데 기지국의 갯수가 N개이고 집중국의 갯수가 K개라면 수신받아야하는 수신의 갯수?는 N-K개 이다 예제로보자면 6-2 = 4개의 수신이 필요하다. 따라서 3은 제외가 된다

0 + 1 + 2 + 2 = 5 가 정답이된다

 

[전체코드]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, K;//센서의 개수, 집중국의 개수
int sensor[10001];//센서의 좌표를 저장하는 배열

int main() {
	cin >> N;
	cin >> K;
	
	for(int i = 0; i < N; i++){
		cin >> sensor[i];
	}
	
	sort(sensor, sensor+N); // 기지국들의 위치 정렬
	
	vector<int> dist(N-1,0);//초기화해주기 귀찮아서 벡터로 받았다 배열로해도 상관없음
	
	for(int i = 0; i < N-1; i++){
		dist[i] = sensor[i+1] - sensor[i];
	}
	
	sort(dist.begin(), dist.end());
	
	int ans = 0;
	
	for(int i = 0; i< N-K; i++)
		ans += dist[i];
		
	cout << ans;
	
	return 0;
}