[백준/Python] 10819번 - 차이를 최대로 성공

문제

백준 10819번 - 차이를 최대로 성공

해결 과정

• 백트래킹으로 풀기
  

시행착오

• 왜 max_ans가 바뀌지 않느냐 그래도 여기까지 쓴 거 대단해
  -> abs(graph[arr[i]] - graph[arr[i+1]]) 이 부분이 문제였음
  -> 어쩐지 계산한 값이 같더라

import sys

n = int(sys.stdin.readline())
graph = list(map(int,sys.stdin.readline().split())) 
arr = []
visited = [False] * n

max_ans = float('-inf')

def dfs(depth):
  global max_ans
  if depth == n:
    ans = 0
    for i in range(n-1):
      ans += abs(graph[i] - graph[i+1])
    max_ans = max(max_ans,ans)
    print(max_ans)
    return 
  for i in range(n):
    if not visited[i]:
      visited[i] = True
      arr.append(i)
      dfs(depth+1)
      visited[i] = False
      arr.pop()
    
  
dfs(0)
print(max_ans)

백트래킹 풀이

import sys

n = int(sys.stdin.readline())
graph = list(map(int,sys.stdin.readline().split())) 
arr = []
visited = [False] * n

max_ans = float('-inf')

def dfs(depth):
  global max_ans
  if depth == n:
    ans = 0
    for i in range(n-1):
      ans += abs(graph[arr[i]] - graph[arr[i+1]])
    max_ans = max(max_ans,ans)
    return 
  for i in range(n):
    if not visited[i]:
      visited[i] = True
      arr.append(i)
      dfs(depth + 1)
      visited[i] = False
      arr.pop()
    
dfs(0)
print(max_ans)

순열 풀이 (더 빠름)

import sys
from itertools import permutations

n = int(sys.stdin.readline())
graph = list(map(int,sys.stdin.readline().split())) 

max_ans = float('-inf')

for i in permutations(graph):
  ans = 0
  for j in range(n-1):
    ans += abs(i[j] - i[j+1])
  max_ans = max(max_ans,ans)

print(max_ans)