[그리디 #20] BOJ 2212 - 센서

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

2212번: 센서

 

 

접근방법

저번에 풀었던 행복유치원과 같은 문제이다.

 

예제 2번을 보면서 한번 살펴보자.

10
5
10 5 20 3 14 6 7 8 18 10 12 15

 

해당 센서를 오름차순으로 정렬하면 다음과 같다.

3 6 7 8 10 12 14 15 18 20

이 세선들을 몇 개씩 묶어서 총 K개의 묶음으로 만들면 된다.

 

이때, 문제의 핵심은 센서 사이의 거리가 짧은 것을 위주로 선택해야한다.

예를 들어 센서의 거리가 다음같다고 하자.

 

3 1 1 2 2 2 1

위 센서간 거리에서 짧은 것끼리 묶어야 센서간 거리의 최소값을 만들 수 있다.

 

3보단 1인 것들을 묶어야 최소로 만들 수 있다.

예를 들어, [ 3 ] [ 1 1 ] [ 2 2 ] [ 2 1 ]  이런 식으로 묶는 것이

[ 3 1 ] [ 1 2] [ 2 2 ] [ 1 ] 보다 더 작은 값을 가질 수 있다. (2 + 4 + 3 vs 4 + 3 + 4)

 

다시 예제로 돌아와서 생각해볼 것은 여러 개를 포함하는 집중국은 몇 개이어야 하는가? 이다.

센서간 거리가 긴 것은 하나의 집중국이 관리하는 것이 효율적이다.

이를 잘 생각해보면, n개의 센서 중 k개는 하나의 집중국이 관리해야한다는 말이다.

 

정리하자면

1. 센서간 거리가 긴 것은 하나의 집중국이 관리해야 한다.

2. 그러기 위해선, 센서간 거리가 짧은 센서들을 묶어서 집중국이 관리해야 한다.

3. 따라서, 하나의 센서만 관리하는 집중국이 최대일 개수는 k개이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <string>
#include <cmath>

#define MAX 9

using namespace std;


int n, k;
vector<int> num;
vector<int> gap;

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

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		num.push_back(tmp);
	}

	sort(num.begin(), num.end());

	for (int i = 0; i < n - 1; i++) {
		int tmp = num[i + 1] - num[i];
		gap.push_back(tmp);
	}

	sort(gap.begin(), gap.end());

	int sum = 0;
	for (int i = 0; i < gap.size() && i < n - k; i++) {
		sum += gap[i];
	}

	cout << sum;
	
}

 

함께보기

https://parvegoongame.tistory.com/123

[그리디 #13] BOJ 13164 - 행복 유치원