소방서 > 문제은행

본문 바로가기


문제은행

1087 : 소방서

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 11 회    시도횟수: 36 회   



큰길이 직선으로 쭉 뻗어있고, 길 옆으로 여러 마을이 자리잡고 있다. 이 문제에서 큰길은 정수가 늘어서 있는 수평선이고, 각 마을의 위치는 수평선 위의 한 점으로 표현된다. 마을들의 좌표가 겹치는 경우는 없다. 두 마을 사이의 거리는 수평선상에 있는 좌표의 차이의 절대값으로 정의된다.

 

우리는 이들 마을이 있는 곳에 소방서를 몇 곳 지으려고 한다. 물론 모든 마을마다 다 짓는 건 아니다. 전체 마을 중 몇 곳을 골라, 그 위치에만 소방서를 짓게 된다. 그리고 우리는 각 마을과 그 마을과 가장 가까운 소방서 사이의 거리의 합이 최소가 되게 하고 싶다.

 

각 마을의 위치와 짓고자 하는 소방서 개수를 입력받는다. 그래서 각 마을과 그 마을과 가장 가까운 소방서 사이 거리의 합으로 있을 수 있는 최소값을 계산하여 출력하고자 한다.


입력 파일의 첫 줄에는 숫자가 두 개 있으며, 각각 마을의수V(1≤V≤300)와 짓고자 하는 소방서의 수P(1≤P≤30, P≤ V)를 나타낸다. 다음 줄 에는 각 마을의 위치를 나타내는 V개의 정수 좌표가 나온다. 좌표는 오름차순으로 정렬되어 있다. 각 좌표 X의 범위는1≤X≤10,000이다.



각 마을과 거기서 가장 가까운 소방서 사이 거리들의 합의 최소값을 나타내는 양의 정수를 출력한다.


[Copy]
10 5
1 2 3 6 7 9 11 22 44 50
[Copy]
9




IOI 2000 day2_2 Post Office

HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.