[backjoon] 10819 차이를 최대로 (python)

문제 101819번: 차이를 최대로

BruteForce 문제

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

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

• 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다.

• 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

예제 입력

6
20 1 15 8 4 10

예제 출력

62

---

문제풀이

| 최댓값 - 최솟값 | + | 2최댓값 - 2최솟값 | ... 으로 코드를 작성하면 배열의 최댓값을 구할 수 있다!
라고 생각했으나.... 잘못 이해했다..
그냥 무조건 다 돌려서 큰 경우의 수를 구하면 되는 것이었다!!!
그러기 위해선 permutations을 이용해서 작성해야한다.

• permutations이란?
  예시)
  1,2,3의 숫자가 적힌 카드가 있을 때, 이 중 두 장을 꺼내는 경우의 수
  -> 12, 13, 21, 23, 31, 32
  'A', 'B', 'C'로 만들 수 있는 경우의 수
  -> 'ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA'

import itertools

pool = ['A', 'B', 'C']
print(list(map(''.join, itertools.permutations(pool)))) 
# 3개의 원소로 수열 만들기
### ['ABC', 'ACB', 'BAC', 'BCA', 'CAB', 'CBA']
print(list(map(''.join, itertools.permutations(pool, 2)))) 
# 2개의 원소로 수열 만들기
### ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

입력 받은 배열을 permutaions로 하면
num_list = permutations(list(map(int, input().split())))
print(list(num_list)) 의 결과가 [(20, 1, 15, 8, 4, 10), (20, 1, 15, 8, 10, 4), (20, 1, 15, 4, 8, 10), ... ] 이렇게 모든 경우의 수 배열을 만들어낸다.
그래서 하나의 배열을 다 돌면서 sum += abs(i[j] - i[j+1])를 구한 뒤 그 중에서 최댓값을 max(maxNum, sum)을 이용해서 구하면 된다!

---

전체 코드

import sys
input = sys.stdin.readline
from itertools import permutations
N = int(input())

num_list = permutations(list(map(int, input().split())))

maxNum = 0

for i in num_list:
    sum = 0
    for j in range(N-1):
        sum += abs(i[j] - i[j+1])
    maxNum = max(maxNum, sum)
print(maxNum)