[python] 2159 케익 배달

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

import sys
INF=sys.maxsize
n=int(input())
sy,sx=map(int,input().split())
cakes=[[sx,sy]]

for _ in range(n):
    sy,sx=map(int,input().split())
    cakes.append([sx,sy])

dist=[[INF for _ in range(5)] for _ in range(n+1)]
for k in range(4):
    dist[-1][k]=1
dist[-1][4]=0

dx=[0,0,1,-1,0]
dy=[1,-1,0,0,0]

for i in range(1,n+1):
    for k in range(5):
        x,y=cakes[i][0]+dx[k],cakes[i][1]+dy[k]
    
        for j in range(5):
            ex,ey=cakes[i-1][0]+dx[j],cakes[i-1][1]+dy[j]        
            dist[i-1][k]=min(dist[i-1][k],abs(ex-x)+abs(ey-y)+dist[i-2][j])

print(min(dist[-2]))

원래 백준 풀이는 안적는데 검색해도 파이썬 풀이가 없길래(틀린 풀이만 있음) 적는다.

dp를 이용했고 다섯개의 점과 다섯개의 점을 계속해서 비교하여 최소값을 갱신하는 식으로 풀었다.

주의할 점은 행과 열을 일반적인 순서와는 다르게 바꿔서 준다는 것