백준 C++ - 센서(2212) 탐욕법

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

2212번: 센서

 

 

1. 집중국이 한 개일 때 최대 수신 거리를 구합니다.

2. 센서 사이의 거리를 구해 temp 배열에 저장합니다.

3. 센서 사이의 거리가 큰 순서대로 정렬합니다. (내림차순)

4. 집중국 - 1만큼 최대 수신 거리에서 센서 사이의 거리를 뺍니다.

5. 끝

#pragma warning(disable:4996)
#include <stdio.h>
#include<algorithm>
using namespace std;
int n, k, ans;
int arr[10100];
int temp[10010];
int check(int x, int y)
{
	return x > y;
}
int main()
{
	scanf("%d%d", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%d", &arr[i]);
	sort(arr, arr + n);
	ans = arr[n - 1] - arr[0];
	for (int i = 1; i < n; i++)
		temp[i - 1] = arr[i] - arr[i - 1];
	sort(temp, temp + n - 1, check);
	for (int i = 0; i < k - 1; i++)
		ans -= temp[i];
	printf("%d", ans);
	return 0;
}

비슷한 문제

https://junsgi.tistory.com/37

C++ - Greedy algorithm ( 헛간 고치기 )