[알고리즘/백준] 11060번 : 점프 점프(python)

처음에 dp리스트를 만들 때 숫자를 지정해 주었다.
N으로 만들어준 이유는 만약 N이 입력이 되면 최대 점프 횟수는 N-1이기 때문이다.

만약 i + j가 N보다 작으면 dp[i+j] = min(dp[i] + 1, dp[i + j])
dp[i] + 1은 한칸만 가는 방법이고 dp[i + j]는 j만큼 가는 방법이다.

dp[N - 1] == N이면 숫자가 바뀌지 않았기 때문에 갈 수 없다고 판단.

N = int(input())
a = list(map(int, input().split()))
dp = [N] * N
dp[0] = 0
for i in range(N):
    for j in range(1, a[i] + 1):
        if i + j < N:
            dp[i + j] = min(dp[i] + 1, dp[i + j])

if dp[N - 1] == N:
    print(-1)
else:
    print(dp[N - 1])