문제

링크

풀이

순열로 푸는 방법과 백트래킹으로 푸는 방법 2가지가 있다. 백트래킹으로 풀어볼까 생각하다가 순열의 구현이 훨씬 간단할 것 같아 순열로 풀었다.

1. 주어진 배열 원소들의 모든 순열을 구한다.

2. 모든 순열의 경우마다 차이의 합을 계산하고, 최댓값을 갱신해준다.

백트래킹의 경우 깊이탐색(dfs)을 수행한다. 순열과 마찬가지로 모든 경우의 수를 탐색하는 것 같다. (이러면 백트래킹을 사용하는 의미가 없지 않나 생각한다...)

1. DFS 탐색을 통해 방문하지 않은 원소를 탐색배열에 넣고 빼면서 순서를 계속 바꿔준다.

2. 끝까지 탐색한 배열의 차이의 합을 정답배열에 추가한다.

3. 정답배열의 최댓값을 구한다.

코드

순열 (내가 푼 풀이)

import sys
from itertools import permutations

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

cases = list(permutations(A))

answer = 0
for case in cases:
    mid_sum = 0
    for i in range(N - 1):
        mid_sum += abs(case[i] - case[i + 1])
    answer = max(mid_sum, answer)

print(answer)

백트래킹

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))