대나무집1 timer 0.001s memory 128MB

진흥이는 N개의 작은 대나무들을 엮어서 기르고 있던 강아지의 집을 지어주려고 한다.

일단 대나무들을 일렬로 세워놓은 후 맨 앞과 맨 끝을 이어서 둥그렇게 엮어서 울타리를 완성한 후에 중간에 문을 낼 예정이다.

대나무들의 길이가 들쭉날쭉하여 대나무를 잘라내어 크기를 똑같이 하려다가 생각해보니 너무 밋밋할 거 같아 있는 그대로 엮어서 사용하기로 했다.

그런데 서로 이웃 대나무끼리의 길이가 너무 많은 차이가 날 경우 제대로 엮을 수가 없어서 튼튼한 울타리를 만들 수가 없다.

7개의 대나무의 길이가 각각 “5 9 3 4 7 6 10” 이라면 이것을 순서를 바꾸지 않고 그대로 엮을 경우 이웃한 대나무의 차가 가장 큰 곳은 맨 앞의 5와 마지막에 있는 10의 차인 5이다.

“7 5 3 4 6 9 10” 과 같이 순서를 바꾸게 되면 이웃한 대나무의 차가 가장 큰 곳은 6과 9 와 차 또는 마지막 10과 맨 앞의 7의 차인 3이 되고 이 경우가 차의 최대값이 최소인 경우가 된다.

주어진 대나무를 이용하여 이웃 대나무간의 길이 차이가 최대인 값이 최소가 되도록 대나무들을 배치했을 때 차이가 최대인 값을 출력하는 프로그램을 작성하라.