[백준 11570번] 환상의 듀엣 (Python3)

import sys
sys.setrecursionlimit(10**5)

N = int(input())
note = [*map(int,input().split())]

def DFS(n1,n2):
  if n2==N-1:
    return
  if not DP[n1][n2+1]:
    DFS(n1,n2+1)
  if not DP[n2][n2+1]:
    DFS(n2,n2+1)
  DP[n1][n2] = min(DP[n1][n2+1]+graph[n2][n2+1],DP[n2][n2+1]+graph[n1][n2+1])

graph = [[0]*N for i in range(N)]
for i in range(N-1):
  for j in range(i+1,N):
    graph[i][j] = abs(note[i]-note[j])
DP = [[0]*N for i in range(N)]
DFS(-1,-1)
print(DP[-1][-1])

2차원이 1차원으로 바뀌고 경로추적을 할 필요가 없어진 경찰차 [백준 2618번] 경찰차 (Python3) (tistory.com) 문제이다.

한마디로 경찰차의 하위호환 문제라고 보면 된다.

 

풀이에 대한 설명은 경찰차 문제 참고