[python] 백준 2159 케익 배달

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

2159번: 케익 배달

 

문제 해결

• 케익을 받는 순서는 정해져 있다.
• 케익을 받을 수 있는 위치는 모두 4가지이다.
• 그래서 출발점-도착점에 따른 최소거리를 각각 구해야한다. 받는 위치가 다르면 다음 순서에 영향을 줄 수 있기 때문
• 이를 구현하기 위해 가장 좋은 것은 DP이다.
• dist[i][j] 는 i번째 사람 케익을 받을 때 동(j=0),서(j=1),남(j=2),북(j=3),(아래 코드는 +중앙(j=4))에서 받고 그때까지의 최소거리를 나타낸다.
• 순수 처음 출발점을 나타내는 dist[0][4] = 0, dist[0][0]=1, dist[0][2] = 1, dist[0][3]= 1 로 초기값을 준다.(나머지 1을 준 이유는 한칸 움직인 것이므로)
• 그 후 출발점-케익 도착자리에 따른 최솟값을 계속 돌리면서 구해준다.
• 그러면 답은 min(dist[-1])이 나온다.

 

CODE

import sys
input= sys.stdin.readline
INF = sys.maxsize

n = int(input())
sy, sx = map(int, input().split())
cakes = [[sx,sy]]

for _ in range(n):
    y, x = map(int, input().split())
    cakes.append([x,y])
dist = [[INF for _ in range(5)] for _ in range(n+1)]

for k in range(4):
    dist[0][k] = 1
dist[0][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][k] = min(dist[i][k],abs(ex-x)+abs(ey-y)+dist[i-1][j])
print(min(dist[-1]))