백준 10819번(차이를 최대로) 파이썬

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

10819번: 차이를 최대로

요즘 구현, 백트래킹, 브루트포스에 관한 문제를 풀어보고 있는중이다.

해당 유형의 코딩테스트 문제가 많이 나오고 있는 추세인거 같다. 그래서 최대한 많은 유형의 문제를 풀어보려고 하는 중이다.

아무래도 완탐,다이나믹 프로그래밍 등 언급한 분야들에 약하다 보니 약점을 커버 하기 위해 문제를 풀어보는 중이다.

이 문제도 그래서 풀어 보았다.

아래는 풀이 코드이다.

import sys 
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
visited = [False]*n
arr2 = []
ans = 0

def dfs():
    global ans
    total = 0
    if len(arr2) == n: # 길이가 n이 되었을때 
        for i in range(n-1):
            total += abs(arr2[i]-arr2[i+1]) # 조건에 나와있는 수식을 실행해준다
        ans = max(total,ans) # 비교하여 최댓값을 바꿔준다
        
    for i in range(n):
        if visited[i] == True: # 이미 작업한 숫자면
            continue # 다음 숫자로 진행한다.
        visited[i] = True # 해당 숫자를 방문처리 해준다.
        arr2.append(arr[i])# arr2에 삽입해준다
        dfs()# 다음 숫자를 넣기위해 재귀를 돌려준다.
        arr2.pop()# 가장 우측 숫자를 빼줘 새로운 배열을 만들 준비를 한다.
        visited[i] = False # 물론 방문처리도 취소해준다.

dfs()
print(ans)