[백준 10819 : PYTHON] 차이를 최대로

문제 풀기 : 10819번

10819번: 차이를 최대로

문제

N개의 정수로 이루어진 배열 A의 정수들을 적절히 배치시켜 다음 식의 최댓값을 구한다.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

(3 ≤ N ≤ 8, -100 ≤ A[N] ≤ 100)

문제풀이

모든 경우의 수를 전부 찾는 완전탐색 문제이다.

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

N개의 정수들에 대한 모든 순서를 구하고 각각의 차이의 합을 비교하여 최대값을 출력한다.

코드 TIP

순열 함수

import itertools

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

 

조합 함수

import itertools

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

 

** itertools는 기본 내장 모듈이다.

참고 : https://docs.python.org/ko/3/library/index.html

전체코드

import sys, itertools

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

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

# 차이가 최대인 값을 넣을 변수
answer = 0

for p in list(permu):
    # 차이의 합을 저장하는 임시 변수
    sumNum = 0

    # 차이의 합 계산
    for i in range(n-1):
        sumNum += abs(p[i]- p[i+1])

    # 차이의 합 최대값 비교
    if sumNum > answer:   # answer = max(sumNum, answer) - 실행시간이 더 걸림
        answer = sumNum

print(answer)