[BOJ][Python] 백준 2159번: 케익 배달

1일 1PS 22일차!

📚 문제

---

골드 2

• 케익을 받을 때 어디서 받을 지를 선택하는 문제이다.
• 출발지의 4방면 * 도착지의 4방면 을 모두 비교한다.
• 가장 처음에는 중심을 제외하고는 1을 거리에 먼저 넣고 파이썬에서는 -1 인덱스로 마지막에 접근할 수 있기에 마지막에 삽입한다.

💡 포인트

---

1. 처음 좌표의 상하좌우와 중심을 설정한다.
2. 루프를 돌면서 처음 ~ 전 좌표 ~ 현 좌표까지의 거리의 최소를 구한다.

💻 코드

---

import sys

INF = sys.maxsize
n = int(input())
cakes = []

for _ in range(n + 1):
    x, y = 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[-1][k] = 1
dist[-1][4] = 0

dx = [1, 0, -1, 0, 0]
dy = [0, 1, 0, -1, 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]))