백준 - 통나무 건너뛰기

백준 - 통나무 건너뛰기

 

 

 문제 설명

 

https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

 

 나의 풀이

 

개인적으로는 조금 어려웠던 문제이다. 만약 원형이 아니라면 가장 적게 차이나는 경우는 그냥 정렬한 상태이지만 이 문제는 원형이기 때문에 처음과 끝이 엄청 차이나게 된다.

 

2 4 5 7 9를 최소 난이도로 배치했을때 2 5 9 7 4가나오는데 이는 가운데로 갈수록 커지는 숫자가 나오는 것을 알 수 있다.

즉 가장 큰 것을 가운데에 놓고 주변에 제일 적게 차이나는 것 두개를 배치하고 그다음 적게 차이나는 것 두개를 배치하면 최소가 된다. 왜냐하면 이 방법이 처음과 끝을 가장 작은수로 배치하면서 가운데로 갈수록 올라가고 가운데에서 끝으로갈수록 내려가게하는 최적의 구조이기 때문이다.

 

그래서 이는 정렬한 값에서 제일 마지막 수부터 -2차이나는 것들 중 가장 큰것을 답으로 놓으면 된다. 

 

import Foundation

let tc = Int(readLine()!)!
for _ in 0..<tc {
    let treeCnt = Int(readLine()!)!
    var trees = readLine()!.components(separatedBy:" ").map{Int($0)!}
    var result = 0
    trees.sort(by: <)
    for i in 2..<trees.count {
        result = max(result, trees[i] - trees[i-2])
    }
    print(result)
}