[BOJ / Python] 10819 차이를 최대로

문제 : 10819번

💪🏻 해결 방법 

1️⃣ 순열로 풀기 

N의 제한이 8이기 때문에 순열로 풀어도 될 것 같다고 판단하였다.

N개의 정수를 오름차순으로 정렬해서 차이를 구하면 최소값을 구할 수 있지만 최대값을 구하려면 전체의 경우의 수를 구해야 한다.

 

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

🏂 Python  itertools 라이브러리  

# 순열 함수

import itertools
itertools.permutations(데이터가 들은 배열 리스트, 나열할 원소 갯수)

# 조합 함수

import itertools
itertools.combinations(데이터가 들은 배열 리스트, 나열할 원소 갯수)

정답 코드 

import sys, itertools

# 입력
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))

# 순열
permutations = itertools.permutations(data, n)

# 최댓값을 담을 변수
result = 0

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

print(result)

🎁 새로 알게 된 사실 

if sumNum > answer:   
    answer = sumNum

result = max(sum, result) # 실행시간이 더 걸림

최댓값을 구할 때 max 함수를 사용하는 것이 if문으로 비교하는 것 보다 실행시간이 조금 더 오래걸림..!