[Python] 백준 / silver / 11060 : 점프 점프

문제 링크 : https://www.acmicpc.net/problem/11060

다이나믹 프로그래밍 문제. 이거 풀면서 내가 다이나믹 프로그래밍에 익숙하지 않다는걸 느꼈다. 메인 점화식은 잘 생각했지만, 부수적인 요소를 생각 못해서 한번 오답처리가 났다. 점화식을 input 에 따라 디테일 하게 짜야되겠다.

for 문 안에 if dp[i] == -1 일 경우를 따로 처리해줘야 했다. 이 조건문을 넣지 않는다면 dp 값이 꼬이는 인덱스들이 생겨버리게 되기 때문에..

파이썬 코드

import sys
N = int(sys.stdin.readline())
miro = list(map(int, sys.stdin.readline().split()))

dp = [-1] * N
dp[0] = 0

for i in range(N):
    if dp[i] == -1:
        continue
    for x in range(1, miro[i]+1):
        if i+x >= N:
            continue
        if dp[i+x] == -1:
            dp[i+x] = dp[i] + 1
        else:
            dp[i+x] = min(dp[i+x], dp[i] + 1)

print(dp[-1])