KOI 전국 2013 고3- 전봇대 > 문제은행 : 정보올림피아드&알고리즘



2636 : 전봇대

제한시간
1000 ms   
메모리제한
32 MB   
해결횟수
86 회   
시도횟수
804 회   

문제

 

일직선상에 N개의 전봇대가 한 줄로 서있다. 

편의상, 일직선을 x-축이라 하고, 전봇대가 서 있는 위치 x0, x2, ..., xN-1은 x-축 상의 x-좌표라고 하자.

x0는 항상 0이고 xi(i≥1)는 양의 정수라고 가정한다.

 

이 전봇대들을 이웃한 두 전봇대 사이의 거리가 모두 일정하도록 일부 전봇대들을 옮기려고 한다. 

이때 이동해야하는 전봇대들의 거리의 합이 최소가 되도록 해야 한다. 

단, x0에 위치한 전봇대는 움직일 수 없고, 이동하는 전봇대들은 정수 좌표 위치로만 이동 가능하다.

 

예를 들어, 아래의 그림 1과 같이 전봇대가 주어져 있다고 하자.

 

 

이 경우 그림 2에서와 같이 x-좌표 6과 9에 위치한 전봇대를 각각 x-좌표 8과 12인 곳으로 이동하면, 

모든 이웃한 전봇대들의 거리는 4로 같고 전봇대의 이동 거리의 합은 5이다.

 

 

하지만 그림 3과 같이 x-좌표 4에 위치한 전봇대만을 x-좌표 3인 곳으로 이동하면, 

이웃한 전봇대들의 거리는 모두 3이고 전봇대의 이동 거리의 합은 1이다.

 

 

전봇대들의 위치 x0, x2, ..., xN-1이 주어지면, 모든 이웃한 전봇대들의 거리가 같도록 전봇대들을 이동할 때(x0에 위치한 전봇대는 고정),

이동거리의 합이 최소가 되도록 하는 프로그램을 작성하시오.

 


입력형식

입력의 첫줄은 전봇대의 수 N(1≤N≤100,000)이 주어진다. 두 번째 줄에는 전봇대의 위치를 나타내는 N개의 서로 다른 x-좌표 xi(i=1, ..., N-1)가 빈칸을 사이에 두고 오름차순으로 주어진다. xi는 정수이고, 0≤xi≤1,000,000,000. <제약조건> • 부분문제 1:   전체 점수 100점 중 11점에 해당하는 데이터에 대해 N≤50이고 xN-1≤100,000이다. • 부분문제 2:   전체 점수 100점 중 21점에 해당하는 데이터에 대해 N≤1,000이고 xN-1≤100,000이다. • 부분문제 3:   전체 점수 100점 중 31점에 해당하는 데이터에 대해 N≤10,000이고 xN-1≤1,000,000,000이다. • 부분문제 4:   전체 점수 100점 중 37점에 해당하는 데이터에 대해 추가적인 제약조건은 없다.

출력형식

출력은 단 한 줄이며, 모든 이웃한 전봇대들의 거리가 같도록 전봇대들의 이동거리 합의 최솟값을 출력한다.

입력 예

4
0 4 6 9

출력 예

1

입력 예

7
0 5 12 15 16 22 23

출력 예

11


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

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

Copyrightⓒ 2010-2019 jungol. All right reserved.

TOP