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

문제링크 : https://www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;

    int N;
    int arr[10001];
    while(T--)
    {
        cin >> N;
        for(int i=0; i<N; i++)
        {
            cin >> arr[i];
        }

        sort(arr, arr+N);

        int result = arr[1] - arr[0];
        for(int i=0; i<N-2; i++)  //정렬후 한칸 건너뛰기
        {
            result = max(result, abs(arr[i]-arr[i+2]));
        }

        cout << result << "\n";
    }

    return 0;

}

 

처음에 그냥 정렬을 하면 맨첫 값과 맨끝 값의 차가 너무 커지게 된다.

이를 보완하기 위해 기존 정렬한 배열에서 한칸만 건너뛰고 높이 차를 구해준다.

 

result에는 처음에 arr[1] - arr[0]을 넣어주는데 이는 양끝값의 차가 가장 최소인 값이다.

이러면 2 4 5 7 9배열을 기준으로 2 5 9 7 4 배열이 생기게된다.

 

2 -> 5

5 -> 9

4 -> 7 (끝 값이 4)