백준 11497 : 통나무 건너뛰기 ( Python )

문제 링크

📌 사용알고리즘 : 정렬

두가지 풀이법이 있습니다. 먼저 첫번째 풀이부터 봅시다.

숫자를 적절히 섞어서 양옆의 차이가 최소로 되도록 만들어 주어야 합니다.
원래라면 정렬한 상태가 답이겠지만 첫번째 값과 마지막 값이 연결되어있습니다.

차이를 최소로 할려면 가장 큰 값과 두번째로 큰 값을 연결해주어야 합니다.
다만 양옆 모두를 봐야하기 때문에 가장 큰 값 주면에는 두번째와 세번째로 큰 값을 연결해줍니다.

N 번째로 큰 값에 대해서 양옆에 N-1,N-2 번째 큰 값을 넣고

N-1,N-2 의 왼쪽과 오른쪽에 N-3,N-4 번째 값을 적절히 넣어주면 정렬상태를 유지하면서 차이를 최소로 만들 수 있습니다.

양옆으로 정렬상태가 제대로 되어있다는 뜻은 차이를 최소로 만들 수 있다는것과 답이 되기 때문에 해를 구할 수 있습니다.

두번째 풀이를 봅시다.

첫번째 풀이에는 직접 해를 만들면서 구했습니다.
하지만 꼭 직접 해를 만들어야지 구할 수 있을까요?

입력에서 주어진 배열을 정렬했다고 해봅시다.
이때 우리는 양옆에 자기자신보다 값이 작은 2개의 수를 둘것입니다.

그렇다면 정렬된 상태의 리스트 L 에서 i 번째 값을 고려할때는 무조건 i-1,i-2 번째 값만 올 수 있습니다.

또한 정렬된 상태이므로 L[i-1]>L[i-2] 이기 때문에 ans = max(ans , L[i]-L[i-1] , L[i]-L[i-2]) 까지 고려할 필요없이 ans = max(ans , L[i]-L[i-2]) 가 정답이 됩니다.

예시로 1,2,3,4,5 를 살펴봅시다.

인덱스가 2일때부터 시작하면 3 옆에는 1 , 4옆에는 2 , 5 옆에는 3이 됩니다.

그러면 1 3 5 4 2 로 적절하게 숫자를 둔다면 항상 해를 구할 수 있습니다.

📌 코드

import sys,math,heapq,time
input=sys.stdin.readline
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

for i in range(I()):
    N=I()
    L=sorted(LMI())
    ans = deque()
    ans.append(L.pop())


    while L:
        left = L.pop()

        if not len(L):
            ans.append(left)
            break

        right = L.pop()

        if max( abs(ans[-1] - left) , abs(ans[0]-right) ) >= max( abs(ans[-1] - right) , abs(ans[0]-left) ):
            ans.appendleft(left)
            ans.append(right)
        else:
            ans.appendleft(right)
            ans.append(left)

    val = 0
    ans.append(ans[0])
    for j in range(len(ans)-1):
        val = max(val , max( abs(ans[j]-ans[j-1]) , abs(ans[j]-ans[j+1]) ) )
    print(val)

for i in range(int(input())):
    N=int(input())
    L=sorted(list(map(int,input().split())))
    ans = 0
    for j in range(2,len(L)):
        ans = max(ans , L[j]-L[j-2])
    print(ans)