[백준/Python] BOJ 10819 - 차이를 최대로

👀 문제

10819번: 차이를 최대로 ✨ 실버 2

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

🔑 키포인트

백트래킹

📍 백트래킹을 이용하여 모든 경우의 수를 생각해 본다.
📍 반례: 정수로 이루어진 배열 A에 중복되는 숫자가 있을 수도 있다는 것. 예) -1 -1 2 3

🚑 처음에 틀렸던 이유

배열에 같은 수가 있는 경우를 생각하지 않아 중복되는 숫자는 모두 방문한 것으로 판단하는 코드를 짰다.

👉 visited 배열을 만들어 방문 여부를 기록하는 것으로 오류 해결

✍️ 코드

# 틀린 이유: 배열에 같은 수가 있을 경우 내가 기존에 짰던 코드는 틀림!
# visited 사용하기 - 같은 수일 경우 방문 여부로 판단

def back(arr):
    global score # 전역 변수로 선언
    if len(arr) == N:
        hap = 0
        for i in range(2, N+1):
            hap += abs(arr[i-2]-arr[i-1])
        score = max(score, hap)
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            arr.append(array[i]) # arr에 추가
            back(arr) # 재귀
            visited[i] = False
            arr.pop() # return으로 돌아오면 pop이 실행, 전 단계로 돌아가는 (백트래킹)

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

back([])
print(score)