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

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

그리디 문제.

문제 접근

통나무의 높이 차를 최소로 하려면 어떤 통나무의 높이와

차이가 제일 적게 나는, 즉 어떤 통나무의 높이 다음으로 크거나,

다음으로 작은 통나무를 인접시켜야 한다.

근데 위 논리를 적용하면 오름차순이나 내림차순으로 배치하게 된다.

오름차순이나 내림차순이면 통나무 높이 배열의 끝과 시작이 인접할 때

차이가 크게 나므로 다른 방법을 채택해야 한다.

이때 최적해는 가운데에 가장 큰 값이나 가장 작은 값을 두고,

우측 좌측에 하나하나씩 그 다음으로 작은 값 혹은 큰 값을

두는 것이다.

따라서 세워지는 통나무는 다음과 같다.

($i$번째 통나무는 정렬된 배열 중 $i$번째임을 뜻한다.)

$2\cdot n$ , $2\cdot {(n-1)}$ , $...$ $2$ , $1$ , $3$ $...$ , $2\cdot {(n-1)-1}$ , $2\cdot {n}-1$

로 배열된다.

이때 인접된 통나무의 차이는 정렬한 후 편리하게 구할 수 있다.

$2\cdot n$과 $2\cdot n-1$이랑 $2$와 $1$이 한칸 차이로 인접한 것을 제외하면,

다른 통나무들은 정렬된 배열에서 두칸 차이 나는 원소와 인접한 것을 볼 수 있다.

이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n; cin >> n; vector<int> arr(n); for(int i=0;i<n;i++) cin >> arr[i];
	sort(arr.begin(),arr.end()); int ans=max(arr[1]-arr[0],arr[n-1]-arr[n-2]);
	for(int i=2;i<n;i++) ans=max(ans,arr[i]-arr[i-2]);
	cout << ans << '\n';
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int t; cin >> t; while(t--) solve();
	return 0;
}