이번 문제는 백트레킹을 이용하여 풀이하였다. 처음에는 수열에 중복된 수가 없을 것이라 생각하고 풀이하여 값에 대한 중복 처리를 하여 틀렸다. 중복된 수가 존재할 가능성을 생각하여, 선택된 수들의 인덱스를 따로 저장하고, 이에 대한 중복 처리를 하여 해결할 수 있었다.

• n을 입력받는다.
• arr을 입력받는다.
• 결과 변수 answer를 0으로 선언한다.
• 순서를 임시로 저장할 임시 리스트 tmp를 선언한다.
• 선택된 수들의 인덱스를 저장할 리스트 idx를 선언한다.
• 주어진 리스트 내부의 수들을 문제의 조건대로 계산하는 함수 get_result를 tmp를 인자로 갖도록 선언한다.
  -> 결과 변수 result를 0으로 선언한다.
  -> 1부터 tmp의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  --> result에 tmp[i-1]-tmp[i]의 절댓값을 더한다.
  -> result를 반환한다.
• 최댓값을 구하는 함수 get_max를 cnt를 인자로 갖도록 선언한다.
  -> answer를 global로 선언한다.
  -> 만약 cnt가 n일 경우,
  --> answer를 answer와 get_result(tmp)의 반환값 중 더 큰 값으로 갱신한다.
  --> 함수를 종료한다.
  -> arr의 길이만큼 반복하는 i에 대한 for문을 돌린다.
  --> 만약 i가 idxs에 존재할 경우, 다음 반복으로 넘어간다.
  --> tmp에 arr[i]를 넣는다.
  --> idxs에 i를 넣는다.
  --> get_max(cnt+1)을 재귀 호출한다.
  --> tmp를 pop한다.
  --> idxs를 pop한다.
• arr을 오름차순 정렬한다.
• get_max(0)을 호출한다.
• answer를 출력한다.

Code

n=int(input())
arr=list(map(int, input().split()))
answer=0
tmp=[]
idxs=[]
def get_result(tmp):
    result=0
    for i in range(1, len(tmp)):
        result+=abs((tmp[i-1]-tmp[i]))
    return result
def get_max(cnt):
    global answer
    if cnt==n:
        answer=max(answer, get_result(tmp))
        return
    for i in range(len(arr)):
        if i in idxs:
            continue
        tmp.append(arr[i])
        idxs.append(i)
        get_max(cnt+1)
        tmp.pop()
        idxs.pop()
arr.sort()
get_max(0)
print(answer)