[백준 10653] 마라톤 2 - Python

문제 보기

 

[사용한 알고리즘]

다이나믹 프로그래밍

 

[알고리즘]

1. 체크 포인트 사이의 거리를 구하여 distance 2차원 배열에 저장합니다.

 - distance[i][j] : i번째 체크포인트와 j번째 체크포인트 사이의 거리입니다.

2. dp 2차원 배열을 INF(=1e10) 값으로 초기화합니다.

 - dp[k][n] : 체크포인트를 최대 k개 건너뛸 수 있는 상황에서 n번째 체크포인트까지 달릴 수 있는 최소거리입니다.

3. 3차원 반복문을 통해서 dp 배열을 채워나갑니다.

 - k값이 1일 때부터 순차적으로 dp 배열을 채워나갑니다.

 - 현재 체크포인트까지 달릴 수 있는 최소거리는 k값을 적게 사용한 곳에서 현재 위치로 이동한 거리와 동일하게 k값을 사용한 곳에서 현재 위치로 이동한 거리를 비교하여 최솟값을 대입하면 됩니다.

 

[코드]

import sys


INF = 1e10
if __name__ == "__main__":
    n, k = map(int, sys.stdin.readline().split())
    point = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

    distance = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            distance[i][j] = abs(point[i][0] - point[j][0]) + abs(point[i][1] - point[j][1])

    dp = [[INF for _ in range(n)] for _ in range(k + 1)]
    dp[0][0] = 0

    # k = 0
    for i in range(1, n):
        dp[0][i] = dp[0][i - 1] + distance[i - 1][i]

    # k = 1, 2, ... k
    for i in range(1, k + 1):
        dp[i][0], dp[i][1] = 0, dp[i - 1][1]
        dp[i][i] = distance[0][i]
        for j in range(1, n):
            for m in range(i, 0, -1):
                if j - m - 1 < 0:
                    continue
                dp[i][j] = min(dp[i][j], dp[i - m][j - m - 1] + distance[j][j - m - 1], dp[i][j - 1] + distance[j - 1][j])

    print(dp[-1][-1])