[파이썬] 백준 알고리즘 No.10819 차이를 최대로

https://www.acmicpc.net/problem/10819

10819번: 차이를 최대로

"""
1. 수를 변경할 수는 없음
2. 주어진 수의 순서를 변경해 최대 차이를 만들기
방법의 수 : N!, 최대 8, 40320 가지 수

"""
def next_permutation(a):
    i = len(a) - 1
    while i > 0 and a[i - 1] >= a[i]:
        i -= 1
    if i <= 0:
        return False
    j = len(a) - 1
    while a[j] <= a[i - 1]:
        j -= 1

    a[i - 1], a[j] = a[j], a[i - 1]
    j = len(a) - 1
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

def calc(a):
    ans = 0
    for i in range(1, len(a)):
        ans += abs(a[i] - a[i - 1])
    return ans
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
while True:
    temp = calc(a)
    ans = max(ans, temp)
    if not next_permutation(a):
        break
print(ans)

재귀를 이용한 방법

 

 

 

from itertools import permutations
n = int(input())
data = list(map(int, input().split()))
ans = 0

for a in permutations(data, n):
    tmp = 0
    for i in range(1, len(a)):
        tmp += abs(a[i] - a[i - 1])
    ans = max(tmp, ans)
print(ans)

itertools의 permutations를 이용한 방법

 

 

STL을 사용할 수 있다면 사용하는게 가장 빠른 시간을 얻을 수 있는 것 같다.