10819 차이를 최대로 _python

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

10819번: 차이를 최대로

abs(A[x]-A[x+1])을 최대로!

예제 입력에 힌트로 어떤경우에 62가 나오는지 설명해주면 좋았을텐데...

그래서 찾아왔다

[8, 20, 1, 15, 4, 10]

 

 

문제 풀이

기본적인 dfs문제로 문제처럼 풀리도록 입력받은 배열을 모두 탐색한다.

그리고 탐색한 배열의 길이가 N이되면 abs(A[x]-A[x+1])이 최대로 하는지 비교하면 된다.

 

 

첫 시도

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
A = []
ans = 0

def dfs():
    if len(A) == N:
        sum = 0;
        for i in range(N-1):
            sum += abs(A[i] - A[i+1])
        global ans
        ans = max(ans, sum)

        
        return
    for i in arr:
        if i not in A:
            A.append(i)
            dfs()
            A.pop()

dfs()

print(ans)

6퍼에서 틀렸다.

생각해보니 if i not in A: 부분이 만약 중복되는 수가 있다면 에러가 날법했다.

 

 

코드

import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int,input().split()))
A = []
visited = [False]*N
ans = 0

def dfs():
    if len(A) == N:
        sum = 0;
        for i in range(N-1):
            sum += abs(A[i] - A[i+1])
        global ans
        ans = max(ans, sum)
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            A.append(arr[i])
            dfs()
            visited[i] = False
            A.pop()

dfs()
print(ans)

180ms