[백준-11060] 점프 점프

나의 코드

import sys
input = sys.stdin.readline

n=int(input())
maze=list(map(int,input().split()))

dp=[1001]*n
dp[n-1]=0
for i in range(n-2,-1,-1):
    if maze[i]==0:
        dp[i]=-1
        continue
    for j in range(1,maze[i]+1):
        if i+j>=n:
            break
        if dp[i+j]<dp[i] and dp[i+j]!=-1:
            dp[i]=dp[i+j]
    if dp[i]==1001:
        dp[i]=-1
    else:
        dp[i]+=1

print(dp[0])

수행시간: 72ms

풀이

나는 맨 마지막부터 처음으로 돌아오면서 최소 점프 횟수를 구하는 방식으로 문제를 풀었다.
예를 들어 입력이
n=10
maze=[1 2 0 1 3 2 1 5 4 2]
이렇게 주어지면
dp[9]는 9번방부터 9번방까지 최소 점프 횟수이므로 0이다.
dp[8]은 8번방부터 9번방까지 최소 점프 횟수이다.maze[8]은 4이므로 9,10,11,12번 방까지 점프할수있고 점프할수있는 방들부터 9번방까지 최소점프횟수에+1한 값이 dp[8]이 된다. 이때 10,11,12번 방은 없으므로 무시해준다. 따라서 dp[8]=1이다.
7번방 부터 9번방까지 최소 점프 횟수는, maze[7]=5이므로 8,9번방 까지 점프할수있다. 따라서 dp[8]과 dp[9]중 최소값에 +1 한 값이 dp[7]이 되고 그 값은 1이다.

만약 maze[i]가 0이면 점프를 할 수 없으므로 dp[i]=-1로 해준뒤 넘어간다.

그리고 i번 방에서 점프가능 방 중에 마지막 방까지 점프할 수 없는 방이 존재한다면 일단 무시하여 모든 점프가능 방을 조사한뒤, 점프 가능 방 중에 맨 마지막까지 점프 할 수 있는 방이 없다면 dp[i]=-1이다.