이전에 점프한 양에 의존하는 다이나믹 프로그래밍

2253번: 점프

 

1번에서 n번으로 이동할건데 처음에는 1칸만 점프할 수 있다

 

그 이후에는 이전에 x칸 점프했으면 이번에는 x-1,x,x+1칸 중 하나를 선택하여 점프할 수 있다

 

물론 1칸 이상 점프해야한다

 

그리고 어떤 돌에는 점프할 수 없다

 

이때 필요한 최소 점프 횟수는?

 

--------------------------------------------------------------------------------------------------------------------------------

 

dp[i][j]를 i칸에 왔을때 점프한 칸의 수가 j칸일때 최소 점프 횟수라고 정의해야할텐데

 

문제가 n이 최대 10000인데 점프할 수 있는 칸 수 j도 10000으로 잡으면 메모리 초과당할 것 같다

 

그래도 다행인건 생각해보면 x칸 점프했으면 이후에는 x-1,x,x+1칸 중 하나를 점프해야하므로

 

가장 많이 점프할 수 있는 칸 수는 얼마일까

 

x = 1부터 시작해서 1,2,3,...으로 1칸씩 늘려가며 점프할 수 있으니까

 

1+2+3.... +m<= 10000인 m을 찾으면 된다

 

m = 140이면 9870

 

그래서 dp[10000][140]정도를 잡으면 된다 

 

10^6정도니까 메모리는 적당

 

이렇게 하면 이제 1번부터 시작하는데 2번 돌에 갈 수 있으면 dp[2][1] = 1

 

그 다음 i = 2,3,...,n에 대하여

 

x = 1,2,..,140에 대해 x-1칸 뛰는 경우 dp[i+x-1][x-1] = dp[i][x] + 1

 

x칸 뛰는 경우 dp[i+x][x] = dp[i][x] + 1

 

x+1칸 뛰는 경우 dp[i+x+1][x+1] = dp[i][x] + 1

 

당연히 중요한 점은 i+x+1, i+x, i+x-1 <= n이어야하고, A[i+x+1], A[i+x-1], A[i+x]가 각각 갈 수 있는 곳이어야한다

 

그 다음 정답은 어떻게 찾지?

 

n번째 칸을 1칸,2칸,,...,140칸 점프해서 이동한 거 모두 유효하므로 dp[n][1],...dp[n][140]중 최솟값

 

당연하지만 x에 따라 불가능한 경우가 있을 수도 있음

 

from sys import stdin

n,m = map(int,stdin.readline().split())

A = [0]*(n+1)

for _ in range(m):

    m = int(stdin.readline())
    A[m] = 1

dp = [[0]*145 for _ in range(n+1)]

if A[2] == 1:

    dp[2][1] = 0

else:
    
    dp[2][1] = 1

for i in range(2,n+1):
    
    for x in range(1,143):
        
        if dp[i][x] > 0:
            
            if i+x <= n and A[i+x] == 0:
                
                dp[i+x][x] = dp[i][x] + 1
            
            if i+x-1 <= n and A[i+x-1] == 0:
                
                dp[i+x-1][x-1] = dp[i][x] + 1
            
            if i+x+1 <= n and A[i+x+1] == 0:
                
                dp[i+x+1][x+1] = dp[i][x] + 1

INF = 10**18
answer = INF

for i in range(143):

    if dp[n][i] > 0:
        
        if answer > dp[n][i]:
            
            answer = dp[n][i]

if answer == INF:
    
    answer = -1
    
print(answer)