APIO 2007_2 Backup- 백업 > 문제은행 : 정보올림피아드&알고리즘




2007 : 백업

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
0 회   
시도횟수
36 회   

문제

당신은 큰 회사들의 컴퓨터 자료를 백업하여주는 정보통신회사를 운영한다. 

자료 백업이 즐거운 일이 아니므로, 당신은 서로 다른 두 회사의 자료를 서로 백업하여 주는 시스템을 개발하여 

당신이 집에서 게임을 즐기는 동안 백업이 이루어지게 하려 한다.

 

모든 회사들은 직선인 길을 따라 위치하고 있다. 

당신은 서로 백업을 하여 줄 두 회사를 짝 지어 주어야 하는데, 두 회사 사이에 네트워크 케이블을 연결 사용하여야한다.

 

네트워크 케이블은 대단히 비쌀 뿐 아니라, 지역 통신 회사에서는 당신에게 오직 k개의 네트워크 케이블을 제공한다. 

– 이 말은 당신이 오직 k 쌍의 회사에만 백업을 할 수 있다는 뜻이다 (전체 2k개의 회사). 

어떤 회사도 두 개 이상의 쌍에 속할 수는 없다 (즉, 여기 2k개의 회사가 모두 다른 회사라는 것을 뜻한다).

 

통신 회사는 네트워크 케이블의 길이를 km 단위로 경비를 부과한다. 

따라서 당신은 가장 짧은 길이의 케이블을 사용하도록 회사들을 k 쌍으로 짝지어야 한다. 

다시 말하자면, 회사들을 짝짓기 하는데, 짝지어진 두 회사 간의 거리들의 전체 합을 최소화 하도록 짝을 지어야 한다는 것이다.

 

예를 들어, 아래 그림과 같이 다섯 개의 고객회사들이 같은 길 위에 위치한다고 하자. 

이 회사들은 각각 길의 출발점에서 기준하여 1 km, 3 km, 4 km, 6 km 그리고 12 km 에 위치하고 있다. 

통신회사에서는 오직 k = 2 케이블만을 제공한다.

 


 

 

이 예에서 최선의 짝 짓기 방법은 첫 번째와 두 번째 회사, 그리고 세 번째와 네 번째 회사를 묶어 주는 것이다. 

k = 2 케이블만을 사용하게 되며, 첫 번째 케이블의 길이는 3 km–1 km = 2 km 이고, 두 번째 케이블의 길이는 6km–4 km = 2km 이다. 

이와 같은 짝짓기는 전체 4 km 의 네트워크 케이블을 사용하게 되며, 실제 가능한 가장 짧은 경우이다.

 


입력형식

입력의 첫 번째 줄에는 정수 n 과 k 가 주어지는데, 각각 길 위의 회사 수(2≤n≤100,000), 그리고 제공되는 네트워크 케이블 수(1≤k≤n/2)를 의미한다. 그 다음 n 줄에는 각각 하나의 정수 s (0≤s≤1,000,000,000) 가 주어지며, 이 정수는 길의 출발점에서 각 회사까지의 거리를 의미한다. 이 정수들은 가장 작은 것에서 가장 큰 것 까지 순서대로 나타난다. 어떤 두 개의 회사도 같은 지점에 있지 않다.

출력형식

출력은 반드시 하나의 양의 정수로 표현되어야 하는데, 이것은 2k 의 서로 다른 회사를 k 쌍으로 묶었을 때 필요한 가장 짧은 전체 네트워크 케이블의 길이이다.

입력 예

5 2 
1 
3 
4 
6 
12

출력 예

4


heap, priority_queue

경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP