백준 10819

import sys


def back_tracking(x):

    # x가 n개라면 => x == len(temp)
    # 조건에 맞게 수를 더해준다.
    if x == n:
        answer.append(sum(abs(m[temp[i + 1]] - m[temp[i]]) for i in range(n - 1)))
        return

    # 반복문을 통해 idx를 temp에 저장
    for i in range(n):
        if i not in temp:
            temp.append(i)
            back_tracking(x + 1) # 백 트래킹
            temp.pop()


n = int(sys.stdin.readline())
m = list(map(int, sys.stdin.readline().split()))
answer = []
temp = []
back_tracking(0)

print(max(answer))

 

 

코드 리뷰

1. back_tracking 함수는 재귀 함수로, 인자 x는 현재까지 선택한 숫자의 개수를 나타낸다.

2. x가 n과 같아지면(temp에 n개의 숫자가 모두 저장되면), temp 배열에 저장된 숫자들로 두 수의 차이의 합을 계산한 후 answer 배열에 추가.

3. 반복문을 통해 temp 배열에 아직 저장되지 않은 숫자들 중 하나를 선택하고(temp.append(i)), 다음 단계(back_tracking(x + 1))를 수행. 이 때 x는 1 증가하게 되며, 이전에 선택한 숫자들(temp)을 포함하여 n개의 숫자를 선택할 때까지 back_tracking 함수를 재귀적으로 호출.

4. 재귀 호출이 끝나면(temp.pop()), 이전에 선택한 숫자를 제거하고 다음 숫자를 선택하도록 반복문을 진행.

5. 최종적으로, answer 배열에서 최댓값을 찾아 출력.

즉, back_tracking 함수를 통해 모든 가능한 순열을 생성하고, 각 순열에 대해 두 수의 차이의 합을 계산하여 최대값을 찾는 방식.