SWEA 6855. 신도시 전기 연결하기 (C++)

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

using namespace std;

int N, K;
int x[1000001];
int dis[1000000];

int main()
{
	int tc;
	scanf("%d", &tc);
	for (int t = 1; t <= tc; t++)
	{
		int answer = 0;
		scanf("%d %d", &N, &K);

		for (int i = 0; i < N; i++)
		{
			scanf("%d", &x[i]);
		}

		for (int i = 0; i < N - 1; i++)
		{
			dis[i] = x[i + 1] - x[i];
		}

		sort(dis, dis + N - 1);

		for (int i = 0; i < N - K; i++)
		{
			answer += dis[i];
		}

		printf("#%d %d\n", t, answer);
	}
}

1. N개의 집 중에서 K개의 발전소를 꼭 설치해야함

2. 그럼 나머지 N - K개는 꼭 전선의 길이를 가지게 됨

3. 각 전선의 길이를 배열에 담아놓음

4. 오름차순 정렬 후 N - K개만 더해보리기

5. 끝