[python] 10819번 차이를 최대로

1. 문제 링크 및 문제

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

1-1 문제 요약

: 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값

2. 해결 방법 생각해보자 ...

1. 전체 경우의 수를 계산해야함 = 백트래킹
   1-1 시작지점, 조건문, 리턴지점
   시작 지점
   : 새로운 배열 [] 생성 , 조건에 맞다면 배열에 추가
   조건문
   : i 는 0-N까지,
   array[i] 를 방문했다면 pass
   아니면
   visited[i]=True
   [새로운 배열].append
   리턴 지점
   : 배열 [] 의 길이가 N 이 되었을 때, 합을 계산

3. 코드

N = int(input())
array = list(map(int,input().split()))
visited = [False]*N
maxAns = 0

def dfs(newarr):
    global maxAns
    
    if len(newarr) == N :
        NewSum = 0
        for i in range(N-1):
            NewSum += abs(newarr[i] - newarr[i+1])
        maxAns = max(maxAns, NewSum)
        return

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            newarr.append(array[i])
            dfs(newarr)
            visited[i] = False
            newarr.pop()

dfs([])
print(maxAns)

! 아차차

아래는 틀린 코드입니다

실수.

1. 반복문에서 total 을 계산한 후에 넘어오는
   visited[i]=False
   newarr.remove
   에서 정확도를 추가해주고자 newarr.remove(array[i]) 를 하였는데
   중복되는 경우는 전혀 생각하지 못했다!
   dfs는 뒤에 추가로 계속 쌓이는 구조이니 newarr.pop() 을 하게되면 맨 뒤의 요소가 알아서 제거될텐데 이상한 실수를 했다.
   역시 방식을 적용할 때에는 완벽한 이해는 필수다 !

    for i in range(N):
        if not visited[i]:
            visited[i] = True
            newarr.append(array[i])
            dfs(newarr)
            visited[i] = False
            newarr.remove(array[i])