[백준] 10819번: 차이를 최대로 - Python

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

 

아이디어

• N의 크기가 3<= N <= 8이다.
• 가능한 모든 경우의 수를 다 계산해도 (가능한 모든 수열)! *(비교횟수) = 8! * 8 = 얼추 32만 
• 모든 경우를 다 보고 비교해도 충분할 것 같음.
• permutations 함수로 가능한 모든 수열을 다 구하고
• 앞뒤 요소 합 연산 을 진행
• 결과값을 이전 연산값과 비교하며 최대값을 찾자

구현

# 모든 경우를 다 비교해봐도 될듯
# N의 최대 크기가 8이라 다 비교해도 8! * 8 는 얼추 32만번 임 충분
from itertools import permutations

N = int(input())
lis = list(map(int, input().split()))

result = 0
for li in permutations(lis):
    total = 0
    for i in range(N - 1):
        total += abs(li[i] - li[i + 1])
    result = max(result, total)

print(result)

 

마무리

입력값의 범위를 확인하고 브루트포스 알고리즘을 사용해도 되는지 잘 판단 할 줄 알고

permutaions 함수를 알면 너무 쉽게 풀린 문제였다.