[백준][10819] 차이를 최대로

• Problem Link : https://www.acmicpc.net/problem/10819

문제

수열이 주어질 때 인접한 두 원소별 차이 합의 최대값을 구하여라

입력

• 첫째 줄, N이 주어진다.
• 둘째 줄, 배열 A의 정수가 주어진다.

출력

• 최대값을 출력한다.

풀이

만들 수 있는 모든 수열 중 차이 합의 최대를 구하는 간단한 문제이다. 순서가 중요하기 때문에 결국 순열을 만드는 것이 관건인 문제인데, 순열을 만드는 것은 백트래킹으로 쉽게 구현할 수 있다.

순열(순서가 있는 수열)이 필요한 문제라면 백트래킹 기법을 항상 염두해두자.

• 어떤 지점을 방문하는 문제나, 특정 순열을 찾는 문제들은 백트래킹으로 시도해볼만 하다.

백트래킹으로 순열을 구하면 해당 순열에서 인접한 원소별 차이 합을 구해 최대값을 구하면 쉽게 해결할 수 있다.

이 문제는 순열을 구하는 백트래킹 기법, 모든 순열에 대해 차이 최대합을 일일히 비교하는 브루트포스 기법을 사용했다고 할 수 있다.

코드

import sys

input = sys.stdin.readline

ans = 0


def dfs(b, cnt):
    global ans
    if cnt == n:
        s = 0
        for i in range(1, len(b)):
            s += abs(b[i - 1] - b[i])
        if s > ans:
            ans = s
        return
    for i in range(n):
        if not visited[i]:
            visited[i] = True
            dfs(b + [a[i]], cnt + 1)
            visited[i] = False


n = int(input())
a = list(map(int, input().split()))
visited = [False] * n
for i in range(n):
    visited[i] = True
    dfs([a[i]], 1)
    visited[i] = False
print(ans)