백준 10819 차이를 최대로 Python

🐸 문제 정보

10819번: 차이를 최대로

 

🤖 알고리즘

백트래킹

 

⏱️ 풀이 시간

24.36m

 

📝 풀이

간단한 백트래킹 문제인데도, 재귀 내부 로직이 잘 안떠올라서 정답을 참고했다ㅠㅠ

임의의 수열을 만드는 재귀 함수인데, 다 풀고나니 그냥 permutation 써도 됐겠다는 생각이 들었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
nums = list(map(int, input().rstrip().split()))
visited = [False] * n
res = 0

def bt(arr):
    global res
    if len(arr) == n:
        temp = 0
        for i in range(n - 1):
            temp += abs(arr[i] - arr[i + 1])
        res = max(res, temp)
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            arr.append(nums[i])
            bt(arr)
            visited[i] = False
            arr.pop()

bt([])
print(res)