백준 2618 - 경찰차 (파이썬)

Answer

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

N = int(input())
W = int(input())
MAX = W + 6

task = [[1, 1], [N, N]]
dp = [[-1] * MAX for _ in range(MAX)]
answer = [[0] * (MAX) for _ in range(MAX)]

def get_distance(a, b):
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def solve(a, b):
    current = max(a, b) + 1
    
    if current == W + 2:
        return 0

    tmp = dp[a][b]
    if tmp != -1:
        return tmp

    x = solve(a, current) + get_distance(task[b], task[current])
    y = solve(current, b) + get_distance(task[a], task[current])

    if x > y:
        answer[a][b] = 1
    else:
        answer[a][b] = 2

    dp[a][b] = min(x, y)
    
    return dp[a][b]


for _ in range(W):
    a, b = map(int, input().split())

    task.append([a, b])

print(solve(0, 1))

i, j = 0, 1

while max(i, j) + 1 < W + 2:
    print(answer[i][j])
    if answer[i][j] == 1:
        i = max(i, j) + 1
    else:
        j = max(i, j) + 1