[BOJ 11497, Python 3] 통나무 건너뛰기

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

11497번: 통나무 건너뛰기

풀이

통나무 건너뛰기 난이도가 인접한 통나무 간의 높이의 차이의 최댓값으로 된다고 합니다.

그러면 일단 정렬을 해서 어떤 순서를 부여해야 한다는 것은 생각해보셨을 겁니다.

 

일단 단순 오름차순으로 해보면 마지막 통나무와 첫번째 통나무의 높이차가 매우 크기 때문에 답이 될 수는 없습니다.

그래서 처음에는 짝수 인덱스만을 사용하여 통나무를 배치하고, 홀수 인덱스만을 사용하여 뒤에 통나무를 이어서 연결하면 됩니다.

이러면 마지막 통나무와 첫 번째 통나무의 비교를 제외한 모든 인접한 통나무의 높이 비교는 오름차순으로 했을 때보다 한 순위 더 밀리지만, 마지막 통나무와 첫 번째 통나무와의 비교는 오름차순때보다 작기 때문에 이 방법이 최적해인 것을 알 수 있습니다.

 

 

코드

for _ in range(int(input())):
    n = int(input())
    arr = sorted([*map(int,input().split())])
    D = [0] * n
    for i in range(0, n, 2):
        D[i//2] = arr[i]
    for i in range(1, n, 2):
        D[-(i//2)-1] = arr[i]
    ans = abs(D[0] - D[-1])
    for i in range(1, n):
        ans = max(ans, abs(D[i] - D[i-1]))
    print(ans)