백준 11497 - 통나무 건너기 (C++)

모든 배열 중에서 최대 높이 차이가 최소인 것을 만들어야 하기 때문에 통나무의 높이를 오름차순이나 내림차순으로 정렬하면 처음과 맨끝이 만나게 되므로 차이가 최대값이 나오게 된다.

해결 방법은 가장 큰 값을 가운데에 두고 왼쪽 오른쪽 번갈아 가면서 놓으면 된다.

-----????----
왼쪽 오른쪽 번갈아 놓기 때문에 중간에서의 높이차는 2칸 떨어진 통나무의 높이차가 될 것이고, 예외로 연결되는 통나무인 첫 번째와 마지막 번째 통나무의 높이차가 1칸 떨어진 통나무의 높이차가 더 추가된다.
그렇게 해서 max 값을 구해주면 그 통나무 건너뛰기의 난이도가 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int T, N, temp;
    cin >> T;
    vector<int> vec;
    vector<int> result;
    for(int i=0; i<T; i++){
        cin >> N;
        for(int j=0; j<N; j++){
            cin >> temp;
            vec.push_back(temp);
        }
        sort(vec.begin(), vec.end());
        for(int k=2; k<N; k++){
            temp = vec[k]-vec[k-2];
            result.push_back(temp);
        }
        cout << *max_element(result.begin(), result.end());
        vector<int>().swap(vec);
        vector<int>().swap(result);
    }
}