소스코드
순열 모듈 사용
import sys
from itertools import permutations
input = sys.stdin.readline
N = int(input().strip())
A = list(map(int, input().strip().split()))
permu_arr = permutations(A)
max_result = 0
for list in permu_arr:
temp_result = 0
for i in range(N-1):
temp_result += abs(list[i] - list[i+1])
max_result = max(max_result, temp_result)
sys.stdout.write(f"{max_result}\n")
Python
복사
재귀함수 사용
import sys
input = sys.stdin.readline
N = int(input().strip())
A = list(map(int, input().strip().split()))
max_result = 0
visited = [False] * (N)
def dfs(depth, seq):
# 재귀함수 종료 조건
if depth == N:
total = 0
for i in range(N-1):
total += abs(seq[i] - seq[i+1])
max_result = max(max_result, total)
return
for i in range(N):
if not visited[i]:
visited[i] = True
seq.append(A[i])
dfs(depth+1, seq)
seq.pop()
visited[i] = False
dfs(1, [])
sys.stdout.write(f"{max_result}\n")
Python
복사
풀이
순열 모듈 사용
•
파이썬의 permutations 함수를 이용하면 리스트의 순열을 만들어낼 수 있습니다.
◦
이렇게 순열을 사용할 수 있는 이유는 배열 A의 정수 개수가 3 이상 8 이하이기 때문입니다. 8이라고 생각하면 8!의 경우의 수가 존재합니다. 8!은 약 4만번으로, 각 경우를 순회하는 것까지 포함한다면 시간복잡도는 O(N! x N)입니다. 시간 초과가 발생하지 않습니다.
•
각 경우의 수를 순회하며 문제의 식에 알맞게 계산을 하고, 최댓값이 되도록 갱신을 이어갑니다.
•
이렇게 완전탐색(브루트포스)로 풀어낼 수 있습니다.
재귀함수 사용
•
하나의 원소가 두 번 들어가면 안되니 방문여부를 체크하기 위한 배열을 만듭니다
•
첫번째부터 차례대로 순회하면서 방문 안 했다면 다음 재귀로 넘겨주기 위해 seq 인자(배열)에 원소를 담습니다. 그리고 방문처리합니다.
•
N개만큼 재귀했다면 결과를 계산해야하므로 depth를 인자로 사용합니다.
◦
만약 depth == N 이라면 문제의 계산식에 맞춰 계산하고 최대값과 비교 & 갱신합니다.
•
재귀 실행을 마치면, seq 인자 배열에서 원소를 하나 제거하고 방문처리를 해제합니다.