[백준] 11497 - 통나무 건너뛰기 [Python(파이썬)]

문제

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

11497번: 통나무 건너뛰기

 

풀이

정렬을 통해 해결할 수 있는 문제였다. 내림차순으로 정렬된 리스트가 하나 있다고 가정해보자. 

List = [L1, L2, L3, ... , Ln] (L1 > L2 >L3 > ... > Ln)

L1을 기준으로 차이가 가장 적게 나는 원소 2개는 L2와 L3일 것이다. 마찬가지로 L2가 기준이라면 L3, L4일 것이고, 이는 계속해서 반복된다. 또한, 내림차순으로 정렬되어 있기 때문에 당연히 Ln - L(n+2) > Ln - L(n+1)이 성립한다.

 

이때, 난이도는 인접한 원소끼리의 높이차의 최댓값에 따라 결정되기 때문에 위 공식에 근거하여 최댓값을 갱신해주면 된다.

for i in range(n-2):
    result = max(result, ls[i] - ls[i+2])

 

코드

import sys

t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline().strip())
    ls = [int(x) for x in sys.stdin.readline().split()]
    ls.sort(reverse=True)
    result = 0
    for i in range(n-2):
        result = max(result, ls[i] - ls[i+2])
    print(result)