문제 이해 단계
문제 이해가 너무 힘들어서 인터넷을 참고하여 문제를 이해하였다.
한마디로 말하면 집중국은 길이로 나타난다.
만약 1개의 집중국으로 위치가 1,7인 센서를 수신하려면
수신 가능 영역은 6(7-1), 길이 같은 느낌으로 해석하면 된다.
즉, K개의 줄로 각 위치에 있는 센서를 연결하는 최소의 수를 구하는 문제이다.
이해를 위해 예제를 그림으로 알아보면 이런 식으로 나타난다.
2개의 집중국을 사용한 수신 가능 영역의 길이의 최솟값이다.
문제 접근 단계
이 문제는 결국 길이를 최소화하기 위해
K개의 그룹으로 나누는 방법을 따지는 문제이다.
길이는 해당 그룹에서 최댓값 - 최솟값으로 나타난다.
길이를 최소화하기 위해서는 당연히 값이 비슷한 센서를 빼야 한다.
따라서 오름차순 또는 내림차순으로 정렬이 필요하다고 생각했다.
다음으로는 그룹을 나눴을 때, 길이를 구하는 수식을 생각해 봤다.
가장 큰 경우는 1개의 그룹으로 나눴을 경우이기 때문에
가장 큰 값 - 가장 작은 값이다.
N개의 센서들을 오름차순 정렬하고, 배열 S [] 담았다고 가정하면
길이의 최댓값 = S [N-1] - S [0]이다.
여기서 i번째를 기준으로 그룹을 나눈다고 가정하자.
예를 들어 예제의 그룹 (1,3,6,6,7,9)에서
2번째 기준으로 그룹을 나눈다고 보면 (1,3)(6,6,7,9)이다.
이때 길이의 합은 5이다.
i번째에서 나누기 때문에 길이의 합을 구해보면
(S [N-1]-S [i+1])+(S [i]-S [0])
= S [N-1]-S [0]-(S [i+1]-S [i])이다.
만약 여기서 j번째를 기준으로 그룹을 한번 더 나눈다면,
위에 식을 전체로 보고 동일한 연산을 하면 된다.
따라서 S [N-1]-S [0]-(S [i+1]-S [i])-(S [j+1]-S [j])이 된다.
즉, K개의 그룹으로 나눌 때는 S [i+1]-S [i]를 K-1번 빼주면 된다.
여기서 알 수 있는 것은 길이의 최솟값을 구하려면 S [i+1]-S [i]이 커야 한다.
즉 답을 구하는 과정은 센서들을 전부 돌면서
S [i+1]-S [i]가 큰 것부터 K개를 고르는 과정이다.
그 후 전체 길이에서 빼주면 그게 답이 된다.
예외로 생각해야 할 부분이
최대 K개의 집중국을 사용하는 것이기 때문에 모두 사용 안 해도 된다.
만약 센서가 6개이고 집중국이 7개라면
각 센서당 하나의 집중국을 사용하면 되기 때문에, 이때의 수신 가능 영역의 길이는 0이 된다.
문제 구현 단계
for (int i = 0; i < N; i++) {
int value;
cin >> value;
v.push_back(value);
}
sort(v.begin(), v.end());
for (int i = 1; i < N; i++) length.push_back(v[i] - v[i - 1]);N개의 센서를 입력받고 이를 내림차순 정렬해 준 후,
최댓값을 구하기 위해 length 배열에 v [i] - v [i -1] 연산을 한 값을 저장했다.
sort(length.begin(), length.end(), greater<int>());
int answer = v[N - 1] - v[0];
for (int i = 0; i < K-1; i++) answer -= length[i];이후 length 벡터를 내림차순 정렬해 준 후
전체 길이에서 큰 것부터 K개만큼 빼준 것이 답이 된다.
if (N <= K) {
cout << "0";
return 0;
}위는 앞서 말했던 예외 처리 부분이다.
센서의 개수보다 집중국의 수가 더 많다면 0을 출력하고 종료한다.
아래는 해당 문제의 전체 코드이다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int N, K;
cin >> N >> K;
if (N <= K) {
cout << "0";
return 0;
}
vector<int> v;
vector<int> length;
for (int i = 0; i < N; i++) {
int value;
cin >> value;
v.push_back(value);
}
sort(v.begin(), v.end());
for (int i = 1; i < N; i++) length.push_back(v[i] - v[i - 1]);
sort(length.begin(), length.end(), greater<int>());
int answer = v[N - 1] - v[0];
for (int i = 0; i < K-1; i++) answer -= length[i];
cout << answer;
}
시행착오
해당 문제와 거의 똑같은 문제를 이전에 풀어봤기 때문에 접근 자체는 어렵지 않았다.
이 유형을 미리 풀어보지 않았다면
굉장히 노가다를 뛰다가 시간초과가 떴을 것 같다.
역시 문제는 많이 풀어보는 게 답인 것 같다.