[BOJ/백준][Gold5] 2212 : 센서 (C++)

 

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

2212번: 센서

[난이도] Gold5
[유형] Greedy

[풀이]
N개의 센서를 위치 기준으로 정렬한 뒤, 센서들 사이의 거리 N-1개를 배열에 넣은 후 다시 정렬을 해준다.
그 뒤 거리가 큰 K-1개의 거리를 뽑아서 그 구간을 제거하면 총 K개의 집중국을 설치한 것과 같은 효과를 가진다.
그러므로 뽑은 K-1개의 거리들을 총 구간에서 빼주면 정답이 된다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int N,K,a[10000];
int main(){
    scanf("%d%d",&N,&K);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    sort(a,a+N);
    int ans = a[N-1]-a[0];
    for(int i=1;i<N;i++) a[i-1] = a[i]-a[i-1]; 
    sort(a,a+N-1);
    for(int i=N-2;i>=N-K && i>=0 ;i--) ans-=a[i];
    printf("%d",ans);
} 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2212.cpp