백준 2212번 센서 (C++)

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

2212번: 센서

 

이 문제의 지문이 잘 이해가 안된다면, 예제 입력 1에 대한 아래 해설을 봐보자.

한 집중국이 [1, 3] 구간을 수신합니다. 영역의 길이는 2입니다.
다른 집중국이 [6, 9] 구간을 수신합니다. 영역의 길이는 3입니다. 둘을 합하면 5가 됩니다.

 

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수들을 선언하고 값을 입력 받는다. 이때 입력받은 센서들의 위치값을 오름차순으로 정렬해준다.

    int n,k,temp,ans=0;
    cin >> n;
    vector<int> v(n);
    vector<int> gap;
    cin >> k;
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v.begin(),v.end());

2. ans의 값은 센서 간의 길이차의 최대값으로 초기화한다. 다음으로 센서간의 거리 차를 gap이라는 vector에 저장해준다.

    ans = v[v.size()-1]-v[0];
    for(int j=1; j<n; j++){
        temp = v[j]-v[j-1];
        gap.push_back(temp);
    }

3. gap vector를 내림차순으로 정렬해준다. 그리고 아래 코드의 for문을 유심히 봐보자.

    sort(gap.begin(),gap.end(),greater<int>());
    for(int i=0; i<k-1; i++){ // 1
        if(i+1>=n) break; // 3
        ans-=gap[i]; // 2
    }

(1) for문이 0부터 k-1까지 진행된다는 점을 기억해두자.

만약 k=2일경우, 1번부터 n개의 센서 가운데 2개의 집중국이 세워질 것이다. 이때 나눠지는 두 개의 그룹 사이에는 1개의 간격차가 발생하게 되고, 이 간격차는 결국 각 센서들의 값 차이중 최대값 1개의 값을 의미할 것이다. 이 경우에 1번부터 n번까지의 센서의 길이에서 해당 최대 간격값을 제거하면 정답이 나온다. 때문에 k-1까지만 for문을 진행하면 된다. 

(2) 위의 해설대로 최대 간격을 최장길이에서 제거해준다.

(3) 만약 i+1>=n일 경우, 이는 센서의 갯수보다 집중국의 설치 가능 갯수가 더 많음을 뜻한다. 더 계산하지 않고 for문을 종료하면 된다.

만약 3번을 간과할 경우 Runtime Error (out of bound)가 발생하니 주의하자

 

4. 정답을 출력한다.

 

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,k,temp,ans=0;
    cin >> n;
    vector<int> v(n);
    vector<int> gap;
    cin >> k;
    for(int i=0; i<n; i++) cin >> v[i];
    sort(v.begin(),v.end());
    ans = v[v.size()-1]-v[0];
    for(int j=1; j<n; j++){
        temp = v[j]-v[j-1];
        gap.push_back(temp);
    }
    sort(gap.begin(),gap.end(),greater<int>());
    for(int i=0; i<k-1; i++){
        if(i+1>=n) break;
        ans-=gap[i];
    }
    cout << ans << "\n";
    return 0;
}