시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB4839127089128.919%

문제

일직선상에 N개의 전봇대가 한 줄로 서있다. 편의상, 일직선을 x-축이라 하고, 전봇대가 서 있는 위치 x0, x1, ..., xN-1은 x-축 상의 x-좌표라고 하자. x0는 항상 0이고 xi(i ≥ 1)는 양의 정수라고 가정한다.

이 전봇대들을 이웃한 두 전봇대 사이의 거리가 모두 일정하도록 일부 전봇대들을 옮기려고 한다. 이때 이동해야하는 전봇대들의 거리의 합이 최소가 되도록 해야 한다. 단, x0에 위치한 전봇대는 움직일 수 없고, 이동하는 전봇대들은 정수 좌표 위치로만 이동 가능하다. 

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

그림 1. 전봇대의 위치

이 경우 그림 2에서와 같이 x-좌표 6과 9에 위치한 전봇대를 각각 x-좌표 8과 12인 곳으로 이동하면, 모든 이웃한 전봇대들의 거리는 4로 같고 전봇대의 이동 거리의 합은 5이다. 

그림 2. 전봇대의 이동 예 1

하지만 그림 3과 같이 x-좌표 4에 위치한 전봇대만을 x-좌표 3인 곳으로 이동하면, 이웃한 전봇대들의 거리는 모두 3이고 전봇대의 이동 거리의 합은 1이다.

그림 3. 전봇대 이동의 예 2

전봇대들의 위치 x0, x1, ..., xN-1이 주어지면, 모든 이웃한 전봇대들의 거리가 같도록 전봇대들을 이동할 때(x0에 위치한 전봇대는 고정), 이동 거리의 합이 최소가 되도록 하는 프로그램을 작성하시오.

입력

입력의 첫 줄은 전봇대의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 전봇대의 위치를 나타내는 N개의 서로 다른 x-좌표 xi(i = 0, ..., N-1)가 빈칸을 사이에 두고 오름차순으로 주어진다. xi는 정수이고, i=0일 때 xi=0, 그 외에는 1 ≤ xi ≤ 1,000,000,000 이다.

출력

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

서브태스크

번호배점제한
111

N ≤ 50, XN-1 ≤ 100,000

221

N ≤ 1,000, XN-1 ≤ 100,000

331

N ≤ 10,000, XN-1 ≤ 1,000,000,000

437

추가적인 제약조건은 없다.

예제 입력 1

4
0 4 6 9

예제 출력 1

1

예제 입력 2

7
0 5 12 15 16 22 23

예제 출력 2

11

힌트

중간 계산 결과와 출력할 값이 32비트 정수형 범위를 벗어날 수 있으니 64비트 정수형을 이용할 것을 권장한다.

출처

Olympiad > 한국정보올림피아드 > KOI 2013 > 고등부 3번

  • 빠진 조건을 찾은 사람: djm03178
  • 데이터를 추가한 사람: sait2000
  • 문제의 오타를 찾은 사람: travis01

채점 및 기타 정보

  • 예제는 채점하지 않는다.