백준 10819번: 차이를 최대로

문제 설명

• 양 옆 인자의 차가 최대가 되도록 배열의 순서를 변경하는 문제입니다.

접근법

• 입력값이 매우 작다는 것에 주목해야 합니다.
  • 다른 알고리즘으로 푸는 문제는 효율성을 위해 N이 큰 경우가 많습니다.
• 8개의 데이터를 줄세우는 경우의 수는 8!가지(40320) 입니다.
• 모든 경우의 수에 대해 계싼하여 가장 큰 값을 구합니다.

정답

N = int(input())
lst = list(map(int,input().split(" ")))

from itertools import permutations

answer = 0
for i in permutations(lst,N):#lst에서 N개를 뽑는 모든 가능한 조합을 가져옵니다
    sum_ = 0
    for t in range(N-1):
        sum_+=abs(i[t]-i[t+1])
    answer = max(answer,sum_)

print(answer)

기타

• 브루트포스 카테고리란 걸 몰랐어도 전수조사를 했을까?
• permutations를 쓰지 않고 직접 구현해야 했다면?
  • BackTest