백준 10819 차이를 최대로 / python

문제 : 10819

풀이 point

N개의 정수로 이루어져있는 리스트들의 요소들 중에서 인접한 요소들 차이의 절대값을 씌운 합을 구했을 때 가장 큰 합을 구하는 문제이다.

N의 값이 굉장히 작으므로 우리는 입력 받은 요소들로 만들 수 있는 모든 순열을 구한 뒤 순열 당 한 번씩 인접한 요소들 차이의 절대값을 씌운 합을 구한다.
그 다음 가장 큰 합이 무엇인지 알아보면 된다.

풀이 방법

python의 경우에는 라이브러리를 통해 쉽게 순열을 구할 수 있다. 아직 순열을 어떻게 만드는지 모르는 사람이라면 직접 구현해보길 권한다.

코드(라이브러리 사용)

import sys
input = sys.stdin.readline

from itertools import permutations

N = int(input())
nums = list(map(int, input().split()))
sequence = list(permutations(nums, N))

ans = 0
for i in sequence:
    sum = 0
    for j in range(N-1):
        sum += abs(i[j]-i[j+1])
    ans = max(ans, sum)

print(ans)

코드(라이브러리 사용x)

#백준, 10819 차이를 최대로
N = int(input())
nums = list(map(int, input().split()))

visit = [False]*N
sequence = [0]*N

ans = 0
def sequencer(depth):
    global ans
    if depth == N:
        sum = 0
        for i in range(N-1):
            sum += abs(sequence[i] - sequence[i+1])
        ans = max(ans, sum)
        return
    for i in range(N):
        if visit[i]:
            continue
        visit[i] = True
        sequence[depth] = nums[i]
        sequencer(depth+1)
        visit[i] = False

sequencer(0)
print(ans)