문제

입력 , 출력

정답

import sys

input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
res = [0 for i in range(n)]
res[0] = 1
if n == 1:
    print(0)
else:
    for i in range(n):
        for j in range(arr[i] + 1):
            if i + j < n and i + j != i and res[i] != 0:
                if res[i + j] == 0:
                    res[i + j] = res[i] + 1
                else:
                    res[i + j] = min(res[i] + 1, res[i + j])
    if res[n - 1] == 0:
        print(-1)
    else:
        print(res[n - 1] - 1)

설명

arr = 입력받은값
res = 현재위치에 올수있는 최소 횟수
비교조건으로는 i + 0 ~ arr[i]의값이 < n 보다 작고
i+j ,즉 j가 0 이 아닐경우 그리고 res[i] , 현재위치에 올수 없었던 경우 가 아니면
res[i+j] == 0 이면 처음 도착했기때문에 res[i+j] = res[i] + 1
처음 도착이 아니였던경우 res[i] + 1 , res[i+j] 중 가장 적은값
출력에 경우에는 res[n-1] 이 0 이면 -1
아니면 res[n-1] - 1 값을 출력
그리고 n = 1일경우에는 0번에 도착하기때문에 0 을 출력

후기

dp 연습을 더 해야겠다...