[백준10819번] 차이를 최대로 / Python3

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력 1

6
20 1 15 8 4 10

예제 출력 1

62

나의 풀이

N이 3부터 8까지로 작은 수로 브루트포스를 이용하여 문제를 해결할 수 있었다. 주어지는 배열을 오름차순으로 정렬을 한 뒤

10972번 다음 순열 문제에서 다음 순열을 찾는 알고리즘을 사용하여 주어지는 배열로 가능한 모든 순열에서 문제에서 주어지는 식을 계산해보고 최댓값을 출력해주었다. 주의할 점은 식에 절대값 기호가 있다는 것을 염두해야한다... 따라서 abs()를 사용하여 더해주면 문제가 쉽게 풀린다.

코드

# 10819번 차이를 최대로
import sys

# 다음 순열 찾는 함수
def nextseq(s):
    k = -1
    for i in range(len(s)-1):
        if s[i] < s[i+1]:
            k = i

    if k == -1:
        return -1

    for j in range(k+1,len(s)):
        if s[j] > s[k]:
            m = j

    s[k], s[m] = s[m], s[k]
    tmp = s[k+1:]
    tmp.sort()

    return s[:k+1] + tmp

# main
n = int(input())
seq = [int(x) for x in sys.stdin.readline().split()]
seq.sort()      # 처음부터 탐색을 위해 오름차순 정렬

maxDis = 0
while True:
    sumDis = 0
    for i in range(len(seq)-1):
        sumDis += abs(seq[i+1] - seq[i])

    maxDis = max(maxDis, sumDis)

    seq = nextseq(seq)
    if seq == -1:
        break

print(maxDis)