[그리디] Python - 11497번, 통나무 건너뛰기

www.acmicpc.net/problem/11497

11497번: 통나무 건너뛰기

import sys
input = sys.stdin.readline


def getMaxDifferenceBetweenAdjacent(nums):
    nums.sort()

    maxDifference = max(abs(nums[0]-nums[1]), abs(nums[-1]-nums[-2]))
    for i in range(N-2):
        maxDifference = max(maxDifference, abs(nums[i]-nums[i+2]))

    return maxDifference


T = int(input())
for _ in range(T):
    N = int(input())
    heights = list(map(int, input().split()))

    maxDifference = getMaxDifferenceBetweenAdjacent(heights)
    print(maxDifference)

 

우선, 최소 난이도가 나오게 되는 통나무의 배치 방법을 생각해보면 다음과 같다.

따라서, 나의 첫 풀이는, left와 right 인덱스를 이동시키면서 저런 식으로 배치하는 식이었다. 하지만, 사실은 굳이 저것을 구현시킬 필요는 없다.

위 사진의 1의 순서로 봤을 때, 각각의 숫자들이 어느 위치의 숫자와 인접하는지에 대한 간단한 패턴이 있는데, 이것을 정리하면 다음과 같다.

1. 일반적인 경우(인덱스가 2~N-2), 현재 인덱스로부터 2칸 떨어진 곳과 인접한다.

2. 인덱스가 0인 경우, 1, 2의 위치와 인접하며, 인덱스가 1인 경우, 0, 3의 위치와 인접한다.

3. 인덱스가 N-1인 경우, N-2, N-3의 위치와 인접하며, 인덱스가 N-2인 경우, N-1, N-4의 위치와 인접한다.

이렇게 글로 쓰니까 복잡해보이지만, 노트에 직접 그려보면 간단하다. 이를 토대로 비교 연산을 해주면 되지만, 굳이 모든 연산을 다 해줄 필요가 없다. 예를 들면, for문으로 순차적으로 비교할 때, i가 2일 때 이미 4와 비교를 해주므로, i가 4일 때 2와 비교하지 않아도 된다.