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

문제 내용.

 

그리디 문제.

모든 통나무를 그냥 정렬하면 당연히 인접한 모든 통나무의 높이 차이가 최소가 되겠지만, 이 문제에서는 양 끝 통나무의 높이 차이도 고려해 줘야 한다.

즉, 양 끝 통나무의 높이 차이만 어떻게 해결하면 된다는 것이다.

모든 통나무가 순차적인 높이로 배열되어야 높이 차이를 최소로 할 수 있을 것임은 쉽게 생각할 수 있다.

그렇다면 n 개의 통나무가 있을 때 n/2개의 통나무는 오름차순으로, 나머지는 내림차순으로 정렬하고, 두 배열을 붙이면 될 것이다.

그리고 오름차순 배열과 내림차순 배열은 각각, 전체 n 개를 정렬했을 때 홀수 번째와 짝수 번째 수들을 담고 있으면 문제에서 요구하는 조건을 만족시킬 수 있을 것이다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
#input=sys.stdin.readline
#print=sys.stdout.write
#sys.setrecursionlimit(100000000)

for _ in range(int(input())):
    n=int(input())
    L=list(map(int,input().split()))
    L.sort()
    q1=deque()
    q2=deque()
    for i in range(0,n,2):
        q1.append(L[i])
    for i in range(1,n,2):
        q2.appendleft(L[i])
    L=list(q1)+list(q2)
    ans=abs(L[0]-L[n-1])
    for i in range(1,n):
        ans=max(ans,abs(L[i]-L[i-1]))
    print(ans)

이게 참 직관으로 풀어서 맞았는데 이걸 설명하려니 쉽지 않다.