[Greedy] 2212번 센서

2212번 센서

 

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

 

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

 

입력

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

 

출력

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

 

예제 입력

6 2
1 6 9 3 6 7

7 3
1 7 8 9 10 11 12

 

예제 출력

5

4

 

해결방법

Greedy Algorithm 유형의 문제이다

이전 프로그래머스 모의고사에서 나왔던 문제였다 (그때도 풀지 못했음)

결국 1시간동안 솔루션을 찾지 못해 구글링을 했다 ㅠㅠ

 

 

⭐️ 솔루션 ⭐️

소팅 & 그리디 로 문제를 접근해야했다

k개의 선분을 만들고 k-1개의 빈칸을 만드는 것이 솔루션이다

 

전체적인 흐름은 아래와 같다

1. 센서의 좌표를 벡터에 입력받는다
2. 센서좌표를 오름차순 정렬 후, 중복제거를 해준다
3. 이 센서들의 거리 차이를 구하여 벡터에 넣어준다
4. 거리 벡터를 내림차순 정렬 후, k-1 개의 빈칸을 만들어 답을 구해낸다

 

 

 

소스코드

문제 해결 시간 : 1h 40m

메모리 : 2300 KB

시간 : 0 ms

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n,k,in,ans;

vector<int> sensor,dist;

bool cmp (int a,int b){
    return a > b;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> k;
    
    for(int i=0; i<n; i++){
        cin >> in;
        sensor.push_back(in);
    }
    
    // 센서의 위치 오름차순 정렬
    sort(sensor.begin(), sensor.end());
    
    // 센서의 중복좌표 제거
    sensor.erase(unique(sensor.begin(), sensor.end()), sensor.end());
    
    // n개의 센서간의 거리 n-1개를 벡터에 삽입
    int pre = sensor[0];
    for(int i=1; i<sensor.size(); i++){
        dist.push_back(sensor[i] - pre);
        pre = sensor[i];
    }
    
    // 거리 차이 내림차순 정렬
    sort(dist.begin(), dist.end(), cmp);
    
    ans = 0;
    for(int i=0; i<dist.size(); i++){
        // k-1개의 빈칸이 존재
        if(i < k-1) continue;
        
        ans += dist[i];
    }
    
    cout << ans << "\n";
    
    return 0;
}