[백준 - Python] 10819. 차이를 최대로 (완전 탐색)

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

10819번: 차이를 최대로

 

코드

from itertools import permutations

n = int(input())
num = list(map(int, input().split()))

per = permutations(num, n)

result = []
for p in per:
    eq = 0
    for i in range(len(p)-1):
        eq += abs(p[i] - p[i+1])
        result.append(eq)

print(max(result))

 

순열 라이브러리를 활용해서 풀었다.

 

주어진 식이 최댓값이 되는 경우를 구하는 방법은

N의 최대값이 8로 작기 때문에

모든 경우를 살펴보고 구하는 방법이 가능하다고 생각했다.

 

 

다른 풀이

이 문제도 백트래킹으로 풀이가 가능한 문제였다.

n = int(input())
a = list(map(int, input().split()))
t = []  # 백트래킹을 적용할 리스트
visited = [0] * n

ans = 0
def dfs(depth):
    global n, ans
    if depth == n:
        total = 0
        for i in range(1, n):
            total += abs(t[i-1] - t[i])
        ans = max(ans, total)
        return
    
    for i in range(n):
        if not visited[i]:
            visited[i] = 1
            t.append(a[i])
            dfs(depth + 1)
            visited[i] = 0
            t.pop()
            
dfs(0)
print(ans)

 

백트래킹 기본 형태를 유지하면서

원하는 깊이까지 도달한 경우에

문제에서 요구한 조건을 만족하는 지 확인헀다.

 

 

해결되지 않은 부분

모든 순열에서 푼 백트래킹 풀이와 유사하게

위의 코드에서 방문 여부 처리 리스트를 없애고

t에 a[i] 포함 여부로 조건을 걸어주면

왜 통과가 안되는지 모르겠다.

 

 

참고 자료

https://aigong.tistory.com/564