[백준][Python] 11060 점프점프

뭔가 요새 DFS로 풀릴것 같으면 DFS하는 습관이 생겼다.

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
check = [False] * 1200
ans = []
v = 0
cnt = 0
def DFS(v,cnt):
    if v>=N-1:
        ans.append(cnt)
        return
    if A[v]==0:
        return
    for i in range(1,A[v]+1):
        if not check[v+i] and not v+i>N-1:
            check[v+i] = True
            DFS(v+i,cnt+1)
            check[v+i] = False

check[0]=True
DFS(0,0)
print(min(ans) if ans else -1)

당연히 시간 초과

N = int(input())
li = list(map(int, input().split()))
dp = [N+1]*N
dp[0] = 0
for i in range(N):
    for j in range(1, li[i]+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[N-1] if dp[N-1] != N+1 else -1)

dp로 하면 간단하다.