boj, 백준) 2212. 센서 (C / C++)

1. 문제 링크

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

2212번: 센서

 

2. 문제 개요

고속도로 위에 N개의 센서를 설치했다. 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 집중국의 수신 가능 영역의 합의 최솟값을 구하는 프로그램을 작성하시오.

 

3. 문제 힌트

Greedy 하게 접근해야 한다.

 

문제에는 최대 K라고 했지만 K개를 쓰는 것이 최소로 나온다.

 

주어진 센서들의 중복을 제거하고 좌표 오름차순으로 정렬한 뒤, 센서들의 간격(구간)을 활용해보자.

구간을 1개 제거하는 것은 그룹을 2개로 나누는 행동과 동일하다.

 

4. 문제 풀이

문제 접근은 무난했는데 구현이 생각보다 헷갈려서 참 고통받았던 문제.

 

풀이처럼 그룹을 전체에서 나누어 나가지 않고 0에서 만들어 나갔는데 계속 Out of bound 예외가 발생해서 결국 코드를 다 지우고 나서야 해결했다.

 

각설하고,

 

우선 집중국의 시선으로 문제를 바라보자. 센서들의 중복을 제거해주기 위해 오름차순 Set에 한번 넣어주고 전부 순회하면서 두 센서 간의 간격을 구하자.

 

구했던 간격들을 최대힙(내림차순)에 삽입해두자. 그 뒤, K개의 그룹을 만들기 위해 K-1개의 간격을 제거하자. 1개의 간격(두 센서 간)을 제거하는 것은 1개의 그룹을 2개로 늘리는 행동과 동일하다. 그리고 거리가 0인 집중국도 집중국에 포함하기 때문에 이렇게 처리할 수 있다.

 

거리가 '매 순간'에 최대인 간선을 제거하면서 K개의 구간을 만들었기 때문에 해는 당연히 최소다.

 

 

5. 코드

#include <cstdio>
#include <set>
#include <queue>
#include <cmath>
using namespace std;

int n, k, ans;
set<int> s;
priority_queue<int> pq;

int main()
{
	scanf("%d", &n);
	scanf("%d", &k);

	for (int i = 0; i < n; ++i){
		int item;
		scanf("%d", &item);
		s.insert(item);
	}

	for (auto iter = ++s.begin(); iter != s.end(); ++iter){
		auto before = iter;
		--before;
		pq.push(abs(*iter - *(before)));
		ans += abs(*iter - *before);
	}


	for (int i = 0; i < k - 1; ++i)
	{
		if (pq.size() == 0)
			break;
		ans -= pq.top();
		pq.pop();
	}

	printf("%d", ans);

	return 0;
}

 

 

 

6. 결과