[백준/파이썬] 10819번 차이를 최대로

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

10819번: 차이를 최대로

기본적인 백트래킹 + 브루트포스 문제이다.

가능한 모든 경우의 수를 해보면서 최댓값을 찾으면 된다. 순열 구하는 문제와 동일하다.

 

만일 아직 백트래킹이 잘 이해가 되지 않는다면, 아주 작은 테스트 케이스를 하나 만들어서 직접 손으로 코드를 따라가보면 된다.

물론 당연히, 시스템 스택을 알고있어야 한다.

import sys
#sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def main():  
  dfs(0)
  
  print(ans)
  
def dfs(depth):
  global tmp
  
  if depth == n:
    calc()
    return
  
  for i in range(n):
    if not visited[i]:
      visited[i] = True
      tmp.append(numbers[i])
      dfs(depth+1)
      tmp.pop()
      visited[i] = False
    
def calc():
  global ans
  sum = 0
  for i in range(len(tmp)-1):
    sum += abs(tmp[i]-tmp[i+1])
    
  ans = max(sum,ans)
  
if __name__ == "__main__":
  n = int(input())
  numbers = list(map(int, input().split()))
  visited = [False for _ in range(n)]
  tmp = []
  ans = -1e9
  main()