10819 - 차이를 최대로

백트래킹에 대해 연습중인데.. 쉽지 않다..

def dfs(pick, visit):
    global min_val
    if len(pick) == n:
        res = 0
        for i in range(len(pick) - 1):
            r = abs(pick[i] - pick[i+1])
            res += r
        min_val = max(min_val, res)

    for i in range(n):
        if visit[i]:
            continue
        visit[i] = True
        pick.append(lis[i])
        dfs(pick, visit)
        visit[i] = False
        pick.pop()

n = int(input())
lis = list(map(int, input().split(" ")))
visit = [False] * len(lis)
min_val = -sys.maxsize
dfs([], visit)
print(min_val)

pick이라는 리스트에 모든 경우의 수를 담는다.. 물론 길이가 6일때만 pick에서의 차이 최대를 구한다. dfs 막줄의 pick.pop()을 해줘야 빠져나오는게 가능하다.

순열로 풀기

import sys
from itertools import permutations

n = int(input())
lis = list(map(int, input().split(" ")))
min_val = -sys.maxsize

for p in permutations(lis, len(lis)):
    c = 0
    for i in range(0, len(p)-1):
        r = abs(p[i] - p[i+1])
        c += r
    min_val = max(c, min_val)

print(min_val)

훨씬 간단하다!