[Brute Force] 백준 10819. 차이를 최대로 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10819번: 차이를 최대로

 

 

2. 문제 풀이

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

 주어진 N개의 정수를 임의의 순서대로 배열해서 최댓값을 구하는 문제입니다.

 왠지 모르게 오름차순 정렬한 뒤에, | A[N-1] - A[0] | + | A[N-2] - A[1] | + ...  이런 식으로 하면 되지 않을까? 하는 생각을 했습니다. 하지만 절댓값의 합이니 | 음수 - 양수 | 또는 | 양수 - 음수 | 가 많아야 하며. 이런 조합을 계속 맞춰주는 마땅한 방법도 없습니다.

 

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 결국, 모든 경우의 수를 고려하는 '브루트 포스' 문제입니다. 수학문제를 풀다보면 자꾸 공식같은 걸 발견해야 할 것 같은 강박관념이 생기긴 합니다. 대부분 그런 공식을 찾아야 제한시간 내에 풀 수 있으니까요. 하지만 이번 문제는 입력값도 최대 8개로 적고, 시간도 넉넉합니다. 이럴 때는 일단 '브루트 포스'부터 해보고 생각해도 늦지 않습니다.

 

 

3. 코드

import itertools

n = int(input())
arr = list(map(int, input().split()))

result = list(itertools.permutations(arr, n))

max = 0
for arr in result:
    sum = 0
    for i in range(n-1):
        sum += abs(arr[i] - arr[i+1])
    if max < sum:
        max = sum
print(max)

 모든 경우의 수를 고려하고자, 순열을 이용합니다.  배열을 나열해야하므로, 순서가 있는 경우의 수입니다. 순열을 사용하기 위해, itertools 라이브러리를 이용합니다. 

 

itertools.permutations(arr, n): arr 리스트에서 n개를 뽑는 순열

 이후 구해진 순열대로 계산하여 최댓값을 구합니다.