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

문제링크 : https://www.acmicpc.net/problem/2212

2212번: 센서

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, arr[10001], dist[10001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N);

    for(int i=0; i<N-1; i++) dist[i] = arr[i+1] - arr[i]; //거리 차이 구하기
    sort(dist, dist+N-1);
    
    int sum = 0;
    for(int i=0; i<N-K; i++) sum += dist[i]; //최소 거리 합 구하기

    cout << sum;

    return 0;
}

 

우선 입력받은 좌표에 대해 정렬을 시행해준다.

정렬한 좌표를 기준으로 해당 좌표 사이의 거리 차이 값을 구해서 따로 배열에 저장해둔다.

거리 차이 값을 구한 배열을 다시 정렬을 해주고, K값에 비례하여 거리 차이가 작은 값 부터 더해주면 된다.

 

예제의 경우 다음과 같다.

6
2
1 6 9 3 6 7

정렬 좌표 : 1 3 6 6 7 9
거리 차이 : 2 3 0 1 2
거리 차이 정렬 : 0 1 2 2 3

거리 차이 값 총 갯수 : N-1
배제해야할 거리 차이 값 갯수 K-1 (기본 사용 1)
필요한 거리 차이 값 갯수 : N-1 - (K-1) = N-K