파이썬 백준 2253 점프

import sys
input = sys.stdin.readline
from collections import defaultdict
 
n, m = map(int, input().split())
TF = [True for i in range(n + 1)]
for i in range(m) : 
    TF[int(input())] = False
 
jump = int((2 * n - 2) ** 0.5) + 1
DP = [[n for i in range(jump + 1)] for i in range(n + 1)]
 
DP[1][0] = 0
for i in range(2, n+ 1) : 
    if TF[i] : 
        jump = int((2 * i - 2) ** 0.5)
        for j in range(1, jump + 1) : 
            if i > j : 
                DP[i][j] = min(DP[i-j][j-1], DP[i-j][j], DP[i-j][j+1]) + 1
 
ans = min(DP[n])
if ans == n : 
    print(-1)
else : 
    print(ans)

IDEA

i번째 돌에 도착하여 다음 점프를 하는 상황을 고려해보자.

같은 i번째 돌에 왔어도 거리 5의 점프로 들어왔을 때와 거리 10의 점프로 들어왔을때의 다음 선택지는 다르다.

즉 점화식을 짤 때 i번째 돌에 들어오는 최소횟수 F(i)를 짜는 것이 아니라, i번째 돌에 거리 j의 점프로 들어오는 최소횟수 f(i, j)를 짜야 한다. 정답에 필요한 F(n)는 f(n, j)들 중 최솟값이 될 것이다. (line 21)

 

점프의 거리는 -1, 0, +1만큼 변할 수 있으니 점화식은 아래와 같다.

f(i, j) = min(f(i-j, j-1), f(i-j, j), f(i-j, j+1)) +1

i번째 돌에 j의 점프로 들어오려면 i-j번째 돌에 들어왔던 이전 점프는 j-1, j, j+1 중 하나여야 하기 때문이다.

 

2차원 DP table을 설계하고 2중 for문으로 이를 채운다.

이때, 문제에서 주어진 작은 돌에 해당하지 않을 때만 DP를 채운다. (line 15)

i에 들어올 때 뛰는 최대 점프 거리는 매번 +1했을 때 root(2(i-1))을 넘지 못하므로, 필요한 범위 내에서만 DP table을 만들고 for문을 돌린다. (line 10 ~ 11, line 16 ~ 17)

 

(line 3의 defaultdict는 써보려 했다가 결국 안쓴게 남은 것 같다. 쓸모없는 줄이다.)