[파이썬/python] 백준 - 10653 마라톤 2

문제

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

---

문제 설명

1. 총 N개의 체크포인트로 구성되어 있는, 마라톤 코스가 존재한다.
2. 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야 마라톤이 종료된다.
3. 게으른 박승원은 몰래 K개의 체크포인트를 몰래 건너뛰려 한다.
   1. 단 1번 체크포인트와 N번 체크포인트는 건너뛰지 않는다.
4. 최대 K개를 건너뛰면서 달릴 수 있을 때, 달려야 하는 최소 거리를 구한다.
   1. 점 (x1,y1)과 (x2,y2) 점 간의거리는  |x1-x2| + |y1-y2| 이다.

 

---

풀이

문제를 이해해보자.

 

N개의 체크포인트가 있고, 최대 K개를 건너뛰면서, 1번에서 N번으로 이동해야한다.

총 1,2,3,4,5의 노드가 있으면 1 -> 3 -> 5 혹은 1 -> 2 -> 5 등의 경로로 이동할 수 있다는 것이다.

 

여기서 하나의 규칙을 발견할 수 있다. 노드는 무조건 순차적으로 증가한다는 것이다. 각 노드에서는 이전에 방문한 노드로 돌아갈 수 없고, 무조건 앞으로만 진행한다. 즉 이전의 정보를 재사용하여 최단 거리를 매 번 갱신할 수 있다. 따라서 DP 알고리즘을 통해 문제를 풀이할 수 있다.

 

이 문제의 핵심은 K에 있다. 최대 5번 건너뛸수 있다고 가정하자.

1,2,3,4,5 총 5개의 노드가 존재한다. 1 -> 3으로 이동하면 총 1회를 건너뛰었다.

그후 3 -> 5로 이동하면 5는 총 2번을 건너뛴 것이 된다.

 

그렇다면 dp는 어떻게 갱신해야 할까? DP[노드][건너 뛴 횟수]로 DP 배열을 만들자. 

[0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0], [0,0,0,0,0,0], 의 DP 배열이 존재한다.

안에 원소는 각각 건너 뛴 횟수라고하겠다.  

 

1 -> 3으로 이동했기 때문에 1개의 노드를 건너 뛰었다. 즉 dp[3][1]은 dp[1][0] + 이동 거리(맨해튼 거리)가 될 것이다.

 

이처럼 각 노드에서 건너 뛴 모든 횟수에서 다음 노드로 이동하는 경우의 수를 모두 구하여 최대 거리를 갱신하면 된다.  

    

1. dp 점화식을 세운다.
   1. dp[e][curr] = 현재 갱신할 지점, [도착노드][건너 뛴 횟수]
   2. dp[e-cost-1][curr-cost] = 건너뛰기 전 노드와 건너 뛰기 전 횟수
2. dp 배열을 갱신하여 최솟값을 탐색한다. 

---

코드

import sys
input = sys.stdin.readline
INF = sys.maxsize
n,k = map(int,input().split())
dist = []
dp = [[INF for _ in range(k+1)] for _ in range(n)]
for _ in range(n):
    dist.append(list(map(int,input().split())))
for i in range(k+1):
    dp[0][i] = 0
def mht(p1,p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

for e in range(1,n):
    for cost in range(k+1):
        if e-cost < 0:
            break
        for curr in range(cost,k+1):
            dp[e][curr] = min(dp[e-cost-1][curr-cost] + mht(dist[e],dist[e-cost-1]), dp[e][curr])

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

---

시간복잡도

• 3차원 반복문을 통해 DP를 갱신했다. 하지만 조건에 의해 총 K번을 돌지 않는다. (e-cost > 0 경우에만)
• 즉 $O(N*K)$정도의 시간복잡도를 예상할 수 있다,
• 최악의 경우 $N = 500, K = 499$이다. 따라서 약 $O(10^6)$의 시간복잡도가 소요된다.