[백준] 10819번 차이를 최대로 - Python / 알고리즘 기초 2/2 - 브루트 포스 - 순열

---

---

---

💡 문제

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

입력

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

출력

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

---

💭 접근

주어진 숫자들의 모든 순열에 대해 주어진 식에 대입하여 계속해서 최댓값을 갱신해주면 되는 문제이다.

이때, 예제에서는 입력이 중복되는 수가 없어서 간과할 수 있는데, 중복되는 숫자가 입력될 수 있다는 것을 유의해야한다.

---

📒 코드

import sys

def dfs(depth):
    global ans

    if depth == n:
        sum = 0
        for i in range(n - 1):
            sum += abs(tmp[i] - tmp[i + 1])
        ans = max(ans, sum)
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            tmp.append(a[i])
            dfs(depth + 1)
            tmp.pop()
            visited[i] = False

n = int(input())
a = list(map(int, input().split()))
visited = [False for _ in range(n)]
tmp = []

ans = -sys.maxsize
dfs(0)

print(ans)

---

💭 후기

처음에 중복되는 수가 입력될 수 있다는 것을 생각하지 못해서 조금 헤맸던 문제....

---

🔗 문제 출처

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

---