[BOJ/백준] 10819번 차이를 최대로 (Python 파이썬)

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

10819번: 차이를 최대로

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	21433	13821	10676	65.078%

 

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1 

6
20 1 15 8 4 10

예제 출력 1 

62

 

---

풀이

이전에 살펴보았던 N과 M 문제를 푸셨다면 매우 쉽게 푸실 수 있습니다.

2022.08.10 - [Algorithm/BackTracking] - [BOJ/백준] N과 M (1~8) (Python 파이썬) [15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657]

[BOJ/백준] N과 M (1~8) (Python 파이썬) [15649, 15650, 15651, 15652, 15654, 15655, 15656, 15657]

 

여기서도 마찬가지로 제약 조건을 생각해보겠습니다.
우선 배열의 순서를 바꿔서 새로운 배열을 완성시키고, 문제에서 정의한 값을 최대로 만들어야 합니다.
이것은 마치 N과 M (1) 문제와 동일하게 중복을 허용하지 않으며 순서에는 제약이 없는 조건과 동일합니다.
또한,최댓값을 구하기 위해서 탐색을 종료한 뒤 결과를 리스트에 담고, 마지막에 해당 리스트의 최댓값을 구해 출력합니다.

from sys import stdin
input = stdin.readline
N = int(input())
num = list(map(int, input().split()))

candidate = []
order = []


def solve(depth):
    if depth == N:
        candidate.append(
            sum(abs(num[order[i + 1]] - num[order[i]]) for i in range(N - 1)))
        return

    for x in range(N):
        if x not in order: #중복 x
            order.append(x)
            solve(depth+1)
            order.pop()


solve(0)
print(max(candidate))

 

탐색 종료시 문제에서 정의한 값을 계산하는 부분을 제외하면, 나머지는 이전에 풀이했던 backtracking 문제와 거의 동일하게 풀이가 가능합니다.