[baekjoon] 백준 10819번(파이썬): 차이를 최대로

문제

10819번: 차이를 최대로

알고리즘

- 백 트래킹을 통해 문제를 수행한다.

- idx를 temp에 저장하고 삭제하는 것을 백트래킹 한다.

- temp에 저장된 idx가 n 개라면 조건에 맞게 수를 더하고 answer에 저장한다.

- answer의 최댓값을 출력한다. 

코드

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))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법