백준 - 차이를 최대로(10819)

Back Tracking + Brute Force

문제

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

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

입력

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

출력

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

---

import sys

n = int(sys.stdin.readline())
li = list(map(int, sys.stdin.readline().split()))

li.sort() # 먼저 정렬 1번
half = (n // 2)
a = sorted(li[:half])    
answer = 0

if n % 2 == 0:
    b = sorted(li[half:])
else:
    b = sorted(li[half + 1:])
    c = li[half]
    
for i in range(len(a)):
        if i != len(a) - 1:
            answer += abs(a[i] - b[i]) + abs(a[i] - b[i + 1])
        else:
            answer += abs(a[i] - b[i])        

if n % 2 != 0:
    last = abs(a[-1] - c) if (abs(a[-1] - c) > abs(b[0] - c)) else abs(b[0] - c)
    answer += last
            
print(answer)

[10, 1, 15, 4, 20, 8]일 때 차이의 절대값이 최대.
주어진 배열을 1번 먼저 정렬하면 [1, 4, 8, 10, 15, 20]
원소의 갯수가 짝수일 때 가운데를 기점으로 b = [10, 15, 20]을 짝수인덱스(0번째 포함) a = [1, 4, 8]을 홀수인덱스에 넣으면 해당 케이스가 완성된다.
만약 원소의 갯수가 홀수라면 가운데 원소를 일단 제외하고 짝수일 경우와 똑같이 계산한 다음 오른쪽 배열의 0번째 b[0]와 왼쪽 배열의 마지막 값 a[-1]과 비교하여 last 값을 더하고 마무리한다.

순열을 이용한 풀이도 있다.

import sys
from itertools import permutations

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
permutation = list(permutations(a, n))
answer = 0

for i in permutation:
    accumulation = 0
    li = list(i)
    for j in range(1, n):
        accumulation += abs(li[j] - li[j - 1])
    answer = max(answer, accumulation)
    
print(answer)

참고)
순열 풀이: https://it-garden.tistory.com/337