— layout: post title: “[백준] 11497” date: 2021-01-26 tags: [problem_solving,python] category : [ps] comments: true —

백준 11497 통나무 건너뛰기

문제 링크
난이도 : 실버1

풀이

높이가 다른 통나무들을 원형으로 놓았을 때, 높이의 차이를 최소로 하는 배열을 찾는 문제입니다. 원형이므로 첫번째 통나무와 마지막 통나무가 이어진다는 점을 주의하여야 합니다.

오름차순으로 통나무를 배열한 후 2칸씩 뛰며 배열에 추가하면 됩니다. 단, 통나무의 개수가 홀수인 경우에는 마지막 통나무가 포함되고, 짝수인 경우에는 포함되지 않으므로, 반대편에서 2칸씩 뛰며 배열에 마저 추가할 때에 유의해주어야 합니다.

코드

# 11497
import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t) :
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	arr1 = arr[::2]
	if(len(arr)%2==1) : arr2 = arr[-2:0:-2]
	else : arr2 = arr[-1:0:-2]
	ans = arr1 + arr2
	tmp = 0
	for i in range(len(ans)-1) :
		tmp = max(tmp,abs(ans[i]-ans[i+1]))
	print(tmp)