[백준] 10819 차이를 최대로 python

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

10819번: 차이를 최대로

손 풀 겸 푼 문제.

백트래킹을 사용해서 모든 조합을 만들어내면 된다. 조건이 별로 걸지 않아서 dfs와 차이가 없다.

 

visit = None
numbers = None
ans = None
def backtrack(ind, limit, total, prev):
    global visit, numbers, ans
    if ind == limit:
        ans = max(ans, total)
        return

    for i in range(limit):
        if visit[i]: continue
        visit[i] = True
        if ind == 0:
            backtrack(ind + 1, limit, total, prev=i)
        else:
            backtrack(ind + 1, limit, total + abs(numbers[i] - numbers[prev]), prev=i)
        visit[i] = False


def main():
    global visit, numbers, ans
    N = int(input())
    numbers = list(map(int, input().split()))
    visit = [False for _ in range(N)]
    ans = 0
    backtrack(0, N, 0, 0)
    print(ans)
if __name__ == "__main__":
    main()