백준 / 10819번 차이를 최대로 - 순열 / Python 파이썬

 

*문제 출처는 백준에 있습니다.

문제 제목: 10819번 차이를 최대로 - 순열

문제 사이트: https://www.acmicpc.net/problem/10819

 

---

나의 풀이

 

순열 구해서 모든 순열에 대해 검사하기

# |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|
a = int(input())
arr = list(map(int, input().split()))

# 차이가 최대가 되려면 가장 큰수 - 가장 작은수
answer = 0
visited = [False] * a
def calculation(lst):
    tmp = 0
    for i in range(1,len(lst)):
        tmp += abs(lst[i] - lst[i-1])
    return tmp
def permutation(n,new_arr):
    global visited, answer
    if len(new_arr) == n:
        result =  calculation(new_arr)
        if result > answer:
            answer = result
        return
    for i in range(len(arr)):
        if visited[i] == False:
            visited[i] = True
            permutation(a,new_arr+[arr[i]])
            visited[i] = False
permutation(a,[])

print(answer)

 

---

※ 알아야 할 것

- 흠 시간초과 날줄알았는데 의외로 괜찮은듯 dfs에서 적절히 return 한것도 도움되는거같다