6855

static int N, K;
static int house[100000];
static int between[100000];

static int cmp(const void * p1, const void * p2)
{
	int n1 = *(int *)p1;
	int n2 = *(int *)p2;
	
	return n1 - n2;
}

static int solution(void)
{
	int ret = 0;

	scanf("%d %d", &N, &K);
	scanf("%d", &house[0]);

	for (int i = 1; i < N; i++)
	{
		scanf("%d", &house[i]);
		between[i - 1] = house[i] - house[i - 1];
	}

	if (K >= N)
		return 0;
	if (K == 1)
		return house[N - 1] - house[0];

	qsort(between, N - 1, sizeof(int), cmp);
	for (int i = 0; i < N - K; i++)
		ret += between[i];

	return ret;
}

이 문제는 풀지는 못했다. 애초에 문제 이해를 잘못하고 있던 것도 있지만, 최소신장트리의 개념이 적용되는 것도 몰랐다.

 

그래서 그 풀이에 대한 내용을 정리해볼까 한다.

일단 두개의 조건에 대한 반환 값은 자명하다.

 

다음은 가장 일반적인 경우에 대한 모델이다.

5개의 집이 있다. 발전소 2개를 건설 할 때, 집 사이에 발전소 하나를 세우는 것 보다는 해당 집이 위치한 곳에 발전소를 세우면 해당 위치에 집으로 전선을 설치 할 필요는 없다.

그래서 나머지 하나의 발전소도 집이 있는 위치에 설치하는 것이 설치한 전선의 길이를 줄이는데 효과적이다.

 

또한 인접한 두 집 사이를 이으면 이는 하나의 최소신장트리가 된다.

 

20 <-20-> 40 <-30-> 70 <-20-> 90 <-60-> 150

 

연결 그래프이고, 20 에서 150을 바로 잇는 것 보다는 이런식으로 잇는 것이 전체 가중치의 합을 최소로 하기 때문이다.

그래서 위 경우 는 발전소를 하나만 세울 때라 고 볼 수 있다.

어느곳에 세우든 전체 필요한 전선의 길이는 같기 때문이다.

그래서 하나의 경우는 반환 값이 자명한 것이다.

 

그러나 발전소 개수가 2개 이상 정점의 개수 미만이면 얘기는 달라진다.

위 MST의 간선 중 발전소 개수를 뺀 개수의 간선 만 선택하고, 더욱이 이를 오름차순으로 선택하면 되는데,

오름차순으로 해야 필요한 전체 전선의 길이가 최소가 되고,

더욱이 원래 MST는 연결 그래프이고,

[A - B - C]  [D - E] 이런 식으로 선택되더라도, 발전소의 개수가 여러개이기 때문에 해당 그룹 내에서는 전기가 공급되기 때문에 논리적으로 연결그래프라 볼 수 있기 때문이다.