요트 경주
면접 대비시간 제한1초메모리 제한128 MB
직선 위에 놓인 표지판들의 위치가 주어질 때, 이전 표지판에서의 거리를 누적해 더한 합이 최소가 되는 방문 순서를 찾는다.
문제
곧 열릴 요트 대회를 위해 조직위원회가 경기를 더 까다롭게 만드는 새로운 방식을 고안했다. 바다 위 한 직선을 따라 여러 개의 부표(표지)가 서로 다른 거리에 놓여 있다. 모든 보트는 이 직선 위의 특정한 한 지점에서 동시에 출발하여 모든 표지를 방문해야 한다. 모든 표지를 방문하면 그 보트의 경기는 끝난다. 우승하려면 모든 표지를 방문하면서 누적 거리의 합을 최소로 만들어야 한다.
첫 번째로 방문한 표지의 누적 거리는 그 표지가 출발 지점으로부터 떨어진 거리이다. 이후에 방문하는 표지의 누적 거리는 바로 직전에 방문한 표지까지의 거리에 그 직전 표지의 누적 거리를 더한 값이다.
출발 표지는 으로 표시한다. 출발 지점의 오른쪽에 있는 표지는 출발 지점으로부터의 거리만큼 양의 정수로, 왼쪽에 있는 표지는 음의 정수로 표시한다. 예를 들어 표지가 위치에 있을 때, 방문 순서 에 대한 누적 거리의 합은 이다(이는 특정한 한 순서에 대해 누적 거리를 계산하는 방법을 보여줄 뿐이며, 반드시 최솟값인 것은 아니다).
주어진 표지들의 위치를 읽어, 가능한 모든 방문 순서 중 누적 거리의 합의 최솟값을 출력하는 프로그램을 작성하라.
또 다른 예로, 표지가 일 때 방문 순서 의 누적 거리 합은 이고, 가장 좋은 순서 의 누적 거리 합은 이다.
입력
첫째 줄에 방문해야 하는 표지의 개수 ()이 주어진다. 출발 표지는 포함하지 않는다.
둘째 줄에 개의 표지 위치가 증가하는 순서로 주어진다(출발 표지는 제외한다). 각 위치는 범위의 정수이다.
출력
모든 방문 순서 중 누적 거리 합의 최솟값을 양의 정수 하나로 출력한다.