백준 파이썬 10819 차이를 최대로

백준 링크:https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

 

모든 경우의 수를 계산하는 브루트포스 + 백트래킹으로 하나씩 탐색하는 방법으로 문제를 풀었다.

 

# 에러코드!!!
n=int(input())
s=list(map(int,input().split()))

arr=[]
result=0

def dfs():
    global result

    if len(arr) == n:
        sum_arr = 0
        for i in range(n-1):

            sum_arr += abs(arr[i]-arr[i+1])
        result = max(result,sum_arr)
        return
    for i in s:
        if i not in arr:
            arr.append(i)
            dfs()
            arr.pop()

dfs()

print(result)

다만 이렇게 할 경우 수열 s에 중복값이 있으면 에러가 나기 떄문에 range값으로 넣도록하였다.

 

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

arr=[]
result=0

def dfs():
    global result
    if len(arr) == n:
        sum_arr = 0
        for i in range(n-1):
            sum_arr += abs(s[arr[i]]-s[arr[i+1]])
        result = max(result,sum_arr)

    for i in range(len(s)):
        if i not in arr:
            arr.append(i)
            dfs()
            arr.pop()

dfs()

print(result)