20200818 // 삼성 SW Expert 아카데미 문제 // 3503

삼성 SW Expert 아카데미 3503번 "초보자를 위한 점프대 배치하기" 문제입니다.

TC = int(input())   
ans = []
for tc in range(1, TC + 1):
    k = "#"+str(tc) + " "
    N = int(input())
    lst = list(map(int, input().strip().split()))
    lst.sort(reverse=True)
    mx = max(lst[0]-lst[1], lst[0]-lst[2])
    for i in range(1, N-2):
        mx = max(mx, lst[i] - lst[i+2])
    mx = max(mx, lst[len(lst)-2] - lst[len(lst)-1])
    k += str(mx)
    ans.append(k)
for e in ans:
    print(e)

어떻게 하면 차이의 최댓값을 줄일 수 있을까 고민해보면 가장 높이가 긴 점프대 양 옆에는 2번째, 3번째로 긴 점프대를

 

배치하면 된다. 그 다음은 2번째로 긴 점프대 옆에 4번째로 긴 점프대를 세우고 3번째로 긴 점프대 옆에 5번째로 긴 점프

 

대를 세우면 차이를 최소로 할 수 있다. 따라서 1->2->4->6... , 1->3->5->7... 로 따라가면서 차이를 계산하여 기존의

 

최댓값과 비교하면 최댓값을 갱신해주면 된다. 마지막에 가장 짧은 점프대와 2번째로 짧은 점프대의 차이까지 계산해서

 

최댓값을 갱신하면 원하는 답을 구할 수 있다.