[백준/10653] 마라톤 (Python3)

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

10653번: 마라톤 2

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:21:00

 

---

 

문제 설명

 

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 N (3 <= N <= 500) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 K 개를 몰래 건너뛰려 한다. (K < N) 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.

젖소 박승원이 체크포인트를 최대 K 개 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?

참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)

 

입력 및 출력

 

입력

첫 번째 줄에 체크포인트의 수 N과 건너뛸 체크포인트의 수 K가 주어진다.

이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x 좌표, 두 번째 정수는 y 좌표이다. (-1000 <= x <= 1000, -1000 <= y <= 1000)

체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원이 한 체크포인트를 건너뛸 때는 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.

 

출력

젖소 박승원이 체크포인트 K 개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

 

입력 예시

5 2
0 0
8 3
1 1
10 -5
2 2

 

출력 예시

4

 

 

---

 

풀이

 

DP로 접근했는데, 이 풀이로는 Pypy3으로만 통과 가능해져버렸다. 아마 시간복잡도가 O(N*K^2)가 되 버려서 그런 듯 하다...

 

i번째 상태에서 남은 체크포인트 스킵이 j개가 남았다고 가정했을 때, 사용하는 체크포인트 값을 k라 두자. 건너갈 수 있는 칸은 1~j+1칸이 된다. 각 k에 대해 다음 식을 만족할 것이다.

 

DP[i+k+1][j-k] = min(DP[i+k+1][j-k], DP[i][k] + manhatten_dist(i, i+k+1)

 

이 경우 시간복잡도는 앞서 말했듯이 O(N*K^2)가 된다. 마지막에 체크포인트를 모두 사용한, DP[N-1][0]값이 정답이 된다.

 

 

 

풀이 코드 (pypy3)

 

MAX = float('inf')

def init() :
  global N, K, checkpoint_list
  N, K = map(int, input().split())
  checkpoint_list = [list(map(int, input().split())) for _ in range(N)]

def cal_dist(a, b) :
  result = 0
  for i in range(2) :
    result += abs(checkpoint_list[a][i] - checkpoint_list[b][i])
  return result

def make_dp() :
  dp = [[MAX]*(K+1) for _ in range(N)]
  dp[0][-1] = 0

  for i in range(N-1) :
    for j in range(K+1) :
      if dp[i][j] == MAX :
        continue
      for k in range(j+1) :
        if i+k+1 >= N :
          break
        dp[i+k+1][j-k] = min(dp[i+k+1][j-k], dp[i][j] + cal_dist(i, i+k+1))

  return dp

def solve() :
  init()
  dp = make_dp()
  print(dp[-1][0])

solve()

풀이 완료~