11060 점프점프

문제

https://www.acmicpc.net/problem/11060

접근 방식

✅ DP 재밌군 .. 점점 정들어가는 중 ,,

- dp[i] : i번째까지 최소 Step 수

j : 1 ~ MAP[i]
- dp[i + j] = min(dp[i] + 1, dp[i + j])

코드

INF = int(1e9)

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

dp = [INF] * n
dp[0] = 0  # 시작점

# bottom-up
for i in range(n - 1):
    if dp[i] == INF or MAP[i] == 0:  # 도달 X, jump X
        continue
    for j in range(1, MAP[i] + 1):
        if i + j < n:
            dp[i + j] = min(dp[i] + 1, dp[i + j])

print(-1 if dp[-1] == INF else dp[-1])