[백준] 10819 : 차이를 최대로

문제

풀이

import sys
import itertools
n = int(sys.stdin.readline())
nlist = list(map(int, sys.stdin.readline().split()))

perm = list(itertools.permutations(nlist, n))

result = []
for i in range(len(perm)):
    s = 0
    for j in range(0, len(perm[i])-1):
        s += abs(perm[i][j]- perm[i][j+1])
    result.append(s)

print(max(result))

다른 사람 풀이 (백트래킹)

import sys

def dfs(depth):
    if depth == N:
        result.append(sum(abs(explore[i] - explore[i + 1]) for i in range(N - 1)))
        return
    for i in range(N):
        if visited[i]:
            continue
        explore.append(A[i])
        visited[i] = 1
        dfs(depth + 1)
        visited[i] = 0
        explore.pop()

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

visited = [0] * N
result, explore = [], []
dfs(0)
print(max(result))