[BOJ]백준 11060번: 점프 점프

www.acmicpc.net/problem/11060

11060번: 점프 점프

전형적인 DP문제이다

iteraton을 이용해서 구현하되, 현재 칸에서 이동 가능한 칸 중 최소 점프 수를 갱신할 수 있다면 해준다

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

dp=[987654321 for _ in range(n+1)]
dp[0]=0
for i in range(len(arr)):
    for j in range(i+1,i+arr[i]+1):
        if j >=n:break
        if dp[i]+1<dp[j]:
            dp[j]=dp[i]+1
if dp[n-1]!=987654321:
    print(dp[n-1])
else: print(-1)

Time complexity: O(n²)

 

😊