백준 BOJ 2212 - 센서

백준 재활 겸 KOI 준비 겸 라이(kks227)님의 알고리즘 강의를 밀고 있다.

그리디 밀면서 오늘 푼 G5.

 

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

2212번: 센서

일단

입력을 보고 센서 좌표가 일직선으로 안들어와서 정렬부터 해줬다.

정렬 하고 보니 테스트케이스에서 3과 6 사이에 연결이 없어야 정답이 나오겠다는 생각이 들었다.

왜 3과 6 사이로 직관했나 생각해보니

3과 6사이의 간격이 가장 커서 뺐다는 결론에 도달했고

그래서 간격을 구해서 정렬을 한번 더해줬다.

 

간격 구한거 값 뽑아보니 3 하나 제외하고 나머지 모든 길이를 더하니

정답에서 요구하는 값이 나온다는걸 알아볼수 있었고

K개로 분리하는데 K-1번 끊어줘야하니까 K-1개의 최댓값을 제거해줬다.

제거하면서 전체 간격의 수보다 K가 큰 경우를 만났는데,

이경우엔 그냥 모든 센서에 집중국을 설치해 답이 0이다.

적당히 처리해주자.

 

https://blog.naver.com/kks227/220775134486

탐욕적 기법(Greedy Algorithm) (수정: 2019-11-23)

매우 양질의 정보가 많으니까

다들 보면 좋을거같다.

#include <bits/stdc++.h>
using namespace std;

int pos[12345] = {0};

vector<int> v;

int main(){
	int n,k;
	cin >> n >> k;
	
	for(int i=0; i<n; i++) cin >> pos[i];
	sort(pos,pos+n);
	
	for(int i=1; i<n; i++) v.push_back(pos[i]-pos[i-1]);
	sort(v.begin(), v.end());
	
	
	for(int i=0; i<k-1; i++) if(!v.empty()) v.pop_back();
	
	int ans = 0;
	for(auto node : v){ ans += node; }
	cout << ans;
	return 0;
}