문제 : https://www.acmicpc.net/problem/10819
목표 :
-
조건 :
- 최대길이가 8이다.
- 숫자의 제한은 -100 <= n <= 100
푸는법 :
- 모든 경우의 수를 다 해보면 permutation하는데 시간복잡도가 O(N!) 이지만 O(8!) = O(40,320)이고,
그 permutation을 하나씩 도는데 O(N)이 걸림으로 O(N!+N) = O(N!)임으로 괜찮다. - 참고로
11! = 39,916,800 (약 3천)
12! = 479,001,600 (약 4억)
임으로 12글자 이상은 permutation을 돌리면 시간초과가 날 가능성이 높다.
from itertools import permutations
_ = input()
ans = 0
nl = permutations(int(i) for i in input().split()) # 시간복잡도 때문에 분리했다.
for k in nl:
sumOfnum = sum(abs(k[j] - k[j+1]) for j in range(len(k)-1))
if sumOfnum > ans : ans = sumOfnum
print(ans)
숏코딩
출처 : 백준 숏코딩의 seiker님 답
from itertools import permutations
_ = input()
print(max(sum(abs(i[j-1]-i[j]) for j in range(1,len(i))) for i in permutations(int(i) for i in input().split())))