백준 10819번 파이썬 | 차이를 최대로

 

문제

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

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

입력

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

출력

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

 

---

풀이

처음에는 가장 큰수와 가장 작은수를 서로 번갈아가면서 계산해봤는데 규칙을 찾기가 힘들었다.

그래서 가장 무식한 방법으로 brute force로 모든 순열을 구한다음에 모든 순열을 for문을 돌려 max를 찾는 방식으로 구했다.

순열을 사용하기 위해 permutations를 사용하였고 이전에 풀었던 스타트 링크 문제와 비슷한듯??

 

# 10819 차이를 최대로
# Brute force

import sys
from itertools import permutations

N = int(sys.stdin.readline())
Nlist = list(map(int, sys.stdin.readline().split()))
ans = 0
members = permutations(Nlist, N)

for member in members:
    member = list(member)
    sum = 0
    for i in range(N - 1):
        sum += abs(member[i] - member[i + 1])
    ans = max(sum, ans)
print(ans)