[BOJ/11497/C++] 통나무 건너뛰기

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

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

• 통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다.
• 통나무 건너뛰기 난이도가 최소난이도가 되었을 때, 그 난이도를 출력해보자.

조건

• 입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

• 이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

풀이

아이디어를 떠올리는게 너무 힘들었던 문제였다. 자신과 차이가 작은 친구를 양옆에 둔다라는 걸 가볍게 생각하고 직관적으로 다가갔으면 빨리 풀었을 것 같은데.. 아쉬웠던 문제이다. 읽었을 때, 그런 느낌이 든다면 그렇게 해보자!

인접한 통나무의 높이차가 최소가 되려면, 또이또이 한것들 끼리 양옆에 두면된다. 정렬은 한다는 의미는 자신과 차이가 작은 순서대로 되기 때문에, 양 옆에 순차적으로 배치한다고 생각을 하면 된다.

편의상 왼쪽,오른쪽 순서대로 배치를 한다고 생각을 했고, 이때 통나무 건너뛰기의 최댓값은 정렬이 되어있는 상태이기 때문에, 자신과 2 차이나는 친구를 빼야한다. deque를 이용해서 직접 앞,뒤에 넣어주는 방법도 훌륭하고, 배열에서 바로 계산을 해도된다.

이때, A2-A1과 , An-1 - An-2는 2차이 나는 친구가 없게 되므로, 따로 계산을 해줘야한다. (갑자기 통나무 크기가 훅 커져서, 그 차이가 최대 난이도가 될 수 있다)

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

int T;
int arr[10001];

int main()
{
  fastio;
  cin >> T;

  while (T--)
  {
    int N;
    cin >> N;
    int ans = 0;

    for (int i = 0; i < N; i++)
    {
      cin >> arr[i];
    }
    sort(arr, arr + N);

    ans = max(ans, arr[1] - arr[0]);
    ans = max(ans, arr[N - 1] - arr[N - 2]);

    for (int i = 0; i < N - 2; i++)
    {
      ans = max(ans, (arr[i + 2] - arr[i]));
    }
    cout << ans << '\n';
  }
  return 0;
}