[D4] SWEA 4111번 무선 단속 카메라 C++ 그리디 알고리즘

 

리뷰

 

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

 

이분 탐색으로 접근했다가 틀리고 그리디로 접근했더니 AC를 받은 문제 

백준에 동일한 문제가 존재한다. 1 + 1 문제

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

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

 

 

전역 변수

• t : 테스트 케이스의 개수를 저장할 변수
• n : 각 테스트 케이스에서 주어지는 센서의 개수를 저장할 변수
• k : 각 테스트 케이스에서 주어지는 집중국의 개수를 저장할 변수

 

함수

없음

 

 

문제풀이

1. t를 입력 받고, t번의 테스트 케이스를 개행해 준다.
2. 각 테스트 케이스 마다 n, k값을 입력 받고, 정수형 벡터 lst를 n크기로 초기화 해준다.
3. lst에 각 센서의 위치 정보를 입력 받고, 오름차순으로 정렬해 준다.
4. 정수형 벡터 dist를 초기화 하고, lst를 순회하며 각 센서의 위치 차이 값을 dist에 push해준다.
5. 모든 센서간 거리의 차이를 구한 후 dist를 내림차순으로 정렬해 준다.
6. 정수형 변수 ans를 0으로 초기화 해주고, dist벡터를 순회해 준다.
7. k - 1과 n - 1 중 작은 값을 기준으로 dist의 값을 ans에 더해준다.
8. 각 테스트 케이스 마다 lst의 맨 끝 요소에서 lst의 맨 앞 요소와 ans를 뺀 값을 출력해 준다.

 

참고 사항

• 위 이미지에서 센서의 범위 내에서 수신 가능 영역이 아닌 수신 가능 영역의 사이 값이 최대인 경우의 값을 더해준다.

 

정답 코드

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

int t, n, k;

int main() {
	cin >> t;
	for (int tc = 1; tc <= t; ++tc) {
		cin >> n >> k;

		vector<int> lst(n);
		for (int i = 0; i < n;++i) cin >> lst[i];
		sort(lst.begin(), lst.end());

		vector<int> dist;
		for (int i = 1; i < n; ++i) dist.push_back(lst[i] - lst[i - 1]);
		sort(dist.begin(), dist.end(), greater<int>());

		int ans = 0;
		for (int i = 0; i < k - 1 && i < n - 1; ++i) ans += dist[i];

		cout << "#" << tc << " " << lst[n - 1] - lst[0] - ans << "\n";
	}
}