[백준-실버2] 10819번 차이를 최대로(백트래킹, 파이썬)

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

<내 코드>

- 백트래킹 연습해야해서 일단 백트래킹으로 구현했다.

- 입력에 같은 숫자가 여러개일수도 있기 때문에  visited 배열을 이용해서 사용한 인덱스를 체크했다.

   (이 부분 때문에 틀렸었음)

- 그리고 순서에 따라 값이 달라지기 때문에 dfs에 파라미터 없이 구현했다.

- stack의 길이가 n과 같아지면 반복문을 통해 그 리스트의 값을 계산하고 max_val과 비교해서 업데이트한다.

n = int(input())
nums = list(map(int, input().split()))
max_val = 0 #절댒값의 합이므로 0으로 설정

stack = []
visited = [False]*n
def dfs():
    global max_val
    if len(stack)==n:
        temp = 0
        for i in range(n-1):
            temp += abs(stack[i]-stack[i+1])
        max_val = max(max_val, temp)
        return
    
    for i in range(n):
        if visited[i] == False:
            stack.append(nums[i])
            visited[i] = True
            dfs()
            visited[i] = False
            stack.pop()
            
dfs()
print(max_val)

 

<permutations 이용 코드>

- 이 문제에선 순서에 따라 값이 달라질수 있기 때문에 순열을 이용해야한다.

from itertools import permutations

n = int(input())
nums = list(map(int, input().split()))

p = list(permutations(nums,n))
max_val = 0
for arr in p:
    temp = 0
    for i in range(n-1):
        temp +=abs(arr[i]- arr[i-1])
    max_val = max(temp, max_val)
    
print(max_val)