[Python/파이썬] 백준 10819번 차이를 최대로

10819번: 차이를 최대로

 

코드

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

ans = -1000
visited = [False]*n


def dfs(depth, total, prev):
    global ans
    if depth == n:
        ans = max(total, ans)
        return
    for i in range(n):
        if not visited[i]:
            tmp = 0
            if depth != 0:
                tmp = abs(prev-a_lst[i])
            visited[i] = True
            dfs(depth+1, total+tmp, a_lst[i])
            visited[i] = False


dfs(0, 0, -1)
print(ans)

 

아직 선택하지 않은 수 중 하나를 골라서 prev와 뺀 결과의 절댓값을 total에 더하고 dfs를 재귀호출하는 함수 dfs를 만들었다. 모든 경우의 수를 다 실행해보므로 브루트포스라고 할 수도 있다.

 

N의 범위가 3 ≤ N ≤ 8으로 작아서 순열로 모든 경우의 수를 구해봐도 될 것 같다.