[BOJ/Python] 10819 : 차이를 최대로

👉 문제 링크

👉 ❌❌❌틀린 코드❌❌❌

중복이 있는 경우를 고려하지 않았다.
예를 들어, 2 -4 -4 0 1 4일 경우에 답은 29지만 밑 코드의 결과는 0이 나온다.
이유는 원래 백트래킹 풀 때 공식 같이 쓰던 코드가 중복을 무시하게 된다.

중복 처리를 깨닫기 전에 이유를 전혀 모르겠어서 다른 사람의 코드를 참고하였다.
대부분 visited 를 써서 방문처리 하였는데 이 외 방법은 떠오르지 않는다ㅠㅠ

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

arr = []
answer = 0

def backTracking():
    global answer

    if len(arr) == n:
        total = 0

        for i in range(n-1):
            total += abs(arr[i] - arr[i+1])
        
        answer = max(answer, total)
        return

    for i in range(n):
        if a[i] not in arr: # -4가 이미 들어가 있기 때문에 중복 처리가 되지 않는다.
            arr.append(a[i])
            backTracking()
            arr.pop()

backTracking()
print(answer)

👉 정답 코드

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

arr = []
visited = [False] * n
answer = 0

def backTracking():
    global answer

    if len(arr) == n:
        total = 0

        for i in range(n-1):
            total += abs(arr[i] - arr[i+1])
        
        answer = max(answer, total)
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            arr.append(a[i])
            backTracking()
            visited[i] = False
            arr.pop()

backTracking()
print(answer)