[백준 10819] 차이를 최대로

문제

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

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

입력

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

출력

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

---

풀이

주어진 배열을 정렬한 후 최댓값을 출력하는 규칙을 찾아보려 했지만 N의 범위를 보고 완전탐색을 먼저 해보기로 했다

 

파이썬에서 지원하는 permutation library를 사용해도 되고, 직접 순열함수를 구현해도 된다

# 배열을 순열로 하여 모든 순서를 탐색
def recursion(idx,N):
    if idx==N:
        s = abs_max(check)
        global ans
        if ans < s:
            ans = s
        return
    for i in range(N):
        if used[i]:
            continue
        used[i]=True
        check[idx] = arr[i]
        recursion(idx+1,N)
        used[i]=False

재귀를 통해 구현해보았다

 

# 주어진 식에 대입
def abs_max(check):
    sum = abs(check[0]-check[1])
    for i in range(3,N+1):
        sum += abs(check[i-2]-check[i-1])
    return sum

모든 경우의 수를 주어진 식에 대입해보며 최댓값을 찾으면 된다

 

필자는 sum = check[0]-check[1] 로 위 함수를 처리해주었다가 99%에서 틀렸습니다가 떠서 괜히 이상한 곳에서 삽질을 조금 했다.