10819번 - 차이를 최대로

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

10819번: 차이를 최대로

# 차이를 최대로
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
l = []
answer = -1e9

def solve(cnt):
    global answer
    if cnt == N:
        total = 0
        for i in range(cnt-1):
            total += abs(l[i]-l[i+1])
        answer = max(answer, total)
        return
    for i in range(N):
        if arr[i] not in l:
            l.append(arr[i])
            solve(cnt+1)
            l.pop()

solve(0)
print(answer)

처음에 문제를 푼 방법은 이랬다. 백트래킹으로 문제를 풀되, 방문체크를 그저 리스트 l에 원소가 있는지 없는지만 판단했다.

하지만 이는 같은 값의 데이터가 들어올 때는 l에 원소를 더할 수 없어 cnt와 N이 동일할 수가 없었다. 즉 total 값을 연산할 수 없기 때문에 answer는 -1e9에서 갱신이 되지 않는다.

 

반례 >> 6 20 1 15 1 4 10

 

따라서 visited 배열을 만들어 방문체크를 진행하여 아래처럼 코드를 수정하였더니 통과했다 :)

 

# 차이를 최대로
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))
visited = [False for _ in range(N)]
l = []
answer = -1e9

def solve(cnt):
    global answer
    if cnt == N:
        total = 0
        for i in range(cnt-1):
            total += abs(l[i]-l[i+1])
        answer = max(answer, total)
        return
    for i in range(N):
        if visited[i] == False:
            visited[i] = True
            l.append(arr[i])
            solve(cnt+1)
            l.pop()
            visited[i] = False

solve(len(l))
print(answer)