[G5] 백준 2212번 센서 C++

리뷰

 

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

고속도로에 집중국을 적절히 배치해서 수신 가능 센서 영역의 길이의 합이 최소가 되게 하는 문제

2일간 문제를 고민했는데 적절한 방법이 떠올라 적용했더니 AC를 받았다.

 

SWEA에 유사 문제가 존재한다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWJHjcFqdyoDFAUH

SW Expert Academy

 

 

전역 변수

• n : 센서의 개수를 저장할 변수
• k : 집중국의 개수를 저장할 변수
• ans : 정답을 저장할 변수
• lst : 센서의 위치를 저장할 정수형 배열

 

함수

없음

 

 

문제풀이

1. n, k값을 입력 받고, n개의 센서 위치 정보를 lst배열에 입력 받아준다.
2. lst배열을 오름차순으로 정렬하고 최소 힙을 사용하는 우선순위 큐 pq를 초기화 한다.
3. n - 1개의 센서간의 위치 차이를 pq에 저장해 준다.
4. pq의 크기가 k - 1개가 될 때 까지 pq에서 요소를 pop해준다.
5. 이후 pq에 남은 요소들을 ans에 더해준다.
6. lst의 n - 1인덱스에서 0번 인덱스 값을 빼주고, ans를 추가로 빼준값을 출력해 준다.

 

트러블 슈팅

1. 처음엔 이분탐색을 통해 접근해 보았는데 AC를 받지 못했다.

 

참고 사항

• 집중국을 k개 최대한으로 활용해 위치가 가까운 센서끼리 묶어주는 작업이 필요하다.
• 이를 반대로 생각해 보면 k개를 사용해 묶은 그룹 사이엔 k - 1개의 빈 공간이 존재한다.
• 해당 빈 공간의 길이를 최대로 만들면 그리디하게 문제를 파훼할 수 있다.

 

정답 코드

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

int n, k, ans;
int lst[10000];

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

	cin >> n >> k;
	for (int i = 0; i < n; ++i) cin >> lst[i];
	sort(lst, lst + n);

	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 1; i < n; ++i) pq.push(lst[i] - lst[i - 1]);

	while (pq.size() > k - 1) pq.pop();
	while (!pq.empty()) {
		ans += pq.top(); pq.pop();
	}
	cout << lst[n - 1] - lst[0] - ans;
}