코드 복사/붙여넣기 하는 당신이 아름답습니다.

2212 : 센서

풀이

각각의 좌표들을 정렬해보자.

그리고 인접한 좌표들의 거리 차이를 구해보자.

그리고 그 거리 차이를 다시 정렬해보자.

k개의 집중국, 다시 말해 k개의 직선을 놓는다면

k-1개의 빈 공간(?)이 생기게 만들 수 있다.

그러므로 방금 정렬한 거리 차이 중에서 가장 큰 값을 k-1개 고르면

집중국이 차지하는 영역(?)의 합이 최소가 될 것이고

답을 구할 수 있다 (!!)

코드

#include <stdio.h>
#include <algorithm>

int n, k, ans, a[10001];

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

	for (int i = 0; i < n; i++) scanf("%d", &a[i]);
	
	std::sort(a, a + n); ans = a[n - 1] - a[0];
	for (int i = n - 1; i > 0; i--) a[i] -= a[i - 1];
	
	std::sort(a + 1, a + n);
	for (int i = n - 1; i > 0 && --k; i--) ans -= a[i];

	printf("%d", ans);

	return 0;
}

아무말

백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이

wookje.kwon's profile image

wookje.kwon

2018-03-15 10:08

Read more posts by this author