11497_통나무 건너뛰기

▶ 실버1

풀이

간단하게 수를 정렬하여 인접한 수의 차의 최대가 최소가 되도록 하면 되는데, 중요한 것은 첫 인덱스와 마지막 인덱스 역시 인접하다고 간주하는 것이다.

 

1, 2, 3, 4, 5가 주어진다면

가장 큰 수인 5를 중심으로 멀어질수록 정렬한 순으로 작아지면 된다.

결국, 1, 3, 5, 4, 2의 순으로 배치해야 최솟값을 구할 수 있다.

 

따라서 일단 주어진 배열을 정렬하고, 2칸 씩 건너뛰면서 수의 차를 확인한다.

n이 짝수일 경우에는 n / 2번을,

n이 홀수일 경우에는 n / 2번 시행한 후 마지막 인덱스도 포함하기 위해 한 번 더 시행한다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <map>
using namespace std;

int arr[10001];
int main(void) {
	ios::sync_with_stdio(NULL);
	cin.tie(0); cout.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n, ans = 0;
		cin >> n;
		for (int i = 0; i < n; i++) {
			cin >> arr[i];
		}
		//정렬
		sort(arr, arr + n);

		for (int i = 1; i < n / 2; i++) {
			ans = max(ans, arr[i * 2] - arr[(i - 1) * 2]);
			ans = max(ans, arr[i * 2 + 1] - arr[(i - 1) * 2 + 1]);
		}
		if (n % 2 == 1) {
			ans = max(ans, arr[(n / 2) * 2] - arr[(n / 2 - 1) * 2]);
		}
		cout << ans << "\n";
	}
}