• 수학 문제인가? 싶어서 나올 수 있는 경우의 수 따져가면서 체크해봄
• 투 포인터 섞어서, 아래와 같은 로직으로 제출
• 테케는 통과지만, 제출 시 틀렸음 → 반례 존재 ㅅㅂ

import math
n = int(input())
arr = list(map(int, input().split()))
arr.sort()

start = 0
end = n-1
mid = math.floor(len(arr) / 2) 
sorted = [arr[mid-1]]
    
while start < end:
    sorted.append(arr[end])
    sorted.append(arr[start])
    start += 1
    end -= 1
    
sum = 0
for i in range(n-1):
    sum += abs(sorted[i] - sorted[i+1])
    

print(sum)

• 보니깐 시간 복잡도 널널하고, BF로 걍 갈겨도 될 것 같음
• 백트래킹 사용해서 문제 해결

import math

n = int(input())
arr = list(map(int, input().split()))

max_sum = 0
result = []
visited = [False] * n

def calculate_sum(result):
    total = 0
    for i in range(n - 1):
        total += abs(result[i] - result[i + 1])
    return total

def solve():
    global max_sum 

    if len(result) == n:  
        max_sum = max(calculate_sum(result), max_sum)
        return
    
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            result.append(arr[i]) 
            solve()
            result.pop()
            visited[i] = False

solve()
print(max_sum)