백준 11297번 통나무 건너뛰기(Python, C++)

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

11497번: 통나무 건너뛰기

 

어떻게 통나무를 배열해야 가장 작은 높이차를 만들 수 있을까?

즉 모든 배열 중에서 최대 높이 차이가 최소인 것을 만들어야 한다.

통나무의 높이를 내림차순으로 정렬하면 처음과 맨끝이 만나게 되므로 차이가 많이 나서 안된다. 그러면 해결 방법은 가장 큰 값을 가운데에 놓고 왼쪽 오른쪽 번갈아 가면서 놓으면 된다. 그렇게 되면 서로 인접한 높이 차이가 오름차순이나 내림차순 정렬을 하였을 때 한 개나 두 개 정도 차이가 되므로 결과적으로 최대 높이 차이는 정렬했을 때의 인덱스 두 개 정도 차이가 된다. 

그럼 그 중에서 가장 큰 값이 최대 높이 차이가 되는 것이고 다른 경우들 중에서는 최소값이 되는 것이다.

 

<python>

t = int(input())

for i in range(t):
    n = int(input())
    a = list(map(int,input().split()))
    a.sort()
    result = 0
    for j in range(2,n):
        c = a[j] - a[j - 2]
        result = max(c, result)
    print(result)

 

 

<C++>

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int t, n;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n;
		int *a = new int[n];
		for (int j = 0; j < n; j++) {
			cin >> a[j];
		}
		sort(a, a+n);
		int result = 0;
		for (int k = 2; k < n; k++) {
			int c = a[k] - a[k - 2];
			result = max(result, c);
		}
		cout << result << '\n';
	
	}
	return 0;
}