[BOJ | Python] 10819번: 차이를 최대로

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

 

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

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

 

 

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

 

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

 

풀이

from itertools import permutations as pm

N = int(input())
A = list(map(int, input().split()))
max_value = 0

for i in pm(A, N):
    temp = 0
    for j in range(N - 1):
        temp += abs(i[j] - i[j + 1] )
    max_value = max(max_value, temp)

print(max_value)

 

입력값 N이 3에서 9까지로, 매우 작은 수임을 통해 "완전탐색"으로 풀이가 가능함을 알 수 있다. 

완전탐색은 모든 경우의 수를 따져보는 방식이기에, 순열(permutations) 모듈을 사용하였다.

순열을 통해 뽑은 자료에 대하여 각각 반복문으로 차이의 합을 구한 후, temp 변수에 저장하였다. 이후 max 메소드로 최댓값을 구하였다.

 

히든 테스트케이스도 없고, 개인적으로 쉽게 푼 문제였다!