백준 알고리즘 파이썬(Python) 10819번 차이를 최대로

---

permutation

순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시한다.

 

순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면
[(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 가 나오게 된다. 즉 순열에서는 (A, B)와 (B, A)는 다른 것이다.

 

from itertools import permutation

arr = ['A', 'B', 'C']
nPr = permutations(arr, 2) #어떤 리스트에서 몇개의 원소를 조합할건지
print(list(nPr))

# 출력 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

 

 

 

---

 

풀이

1. 주어진 배열 원소들의 모든 순열을 구한다.
2. 모든 순열의 경우마다 차이의 합을 계산하고, 최댓값을 갱신해준다.

import sys
from itertools import permutations

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

cases = list(permutations(a))
print(cases)

answer = 0
for cases in cases:
    check = 0
    for i in range(n-1):
        check += abs(cases[i] - cases[i+1])
    answer = max(answer, check)
print(answer)

permutation을 사용할 때 뒤에 몇 개의 원소를 사용할지 정해주지 않았으므로 들어오는 리스트를 모두 permutation 해준다. 

이는 문제에서 N의 개수가 3 ~ 8개로 지정되어 있으므로 리스트의 원소개수가 최대로 들어와도 처리해야 될 수가 8! 임으로 시간이 그렇게 많이 들지 않기 때문에 쓸 수 있다. 즉 완전 탐색이 가능하다는 이야기이다.

 

따라서 모든 경우 원소들끼리의 차이의 절댓값의 합을 max함수를 이용하여 갱신해주고 마지막에 answer을 출력해주면 된다.