[백준 11497번] 통나무 건너뛰기 (java)

11497번: 통나무 건너뛰기

 

통나무를 선형으로 배열하는 것이 아니라 원형으로 배열하기 때문에 처음과 끝이 만난다.

그러므로 통나무를 단순히 오름차순, 혹은 내림차순으로 정렬하면 최소 난이도를 구할 수 없다.

 

예를 들어 오름차순으로 정렬하면 가장 왼쪽에는 최소값, 가장 오른쪽에는 최대값이 배치되는데, 원형이기 때문에 둘 사이의 차이도 난이도에 포함된다. 최대값에서 최소값을 뺀 값은 가장 큰 차가 되므로 최소 난이도를 구할 수 없다.

 

그래서 최소 난이도를 구하기 위해서는 중간에 위치한 통나무의 길이가 가장 크고 가장자리로 갈수록 작아지는 형태로 정렬을 해야 한다.

 

일단 입력받은 통나무 길이를 우선순위 큐에 넣고, 큰 값부터 꺼낸다.

새로운 배열에 가운데 위치부터 시작해서 점점 양옆으로 위치를 옮겨가며 큰수에서 작은수 차례대로 배열에 담는다. 

그 다음 인접한 통나무끼리의 길이 차이를 구하고 가장 최대값이 최소 난이도가 된다.

 

소스코드 :