[백준/python] 11060 - 점프 점프

11060번: 점프 점프

import sys

n = int(input())
miro = list(map(int, input().split()))
dp = [1000 for _ in range(n)]
dp[0] = 0

for i in range(n):
    for j in range(1, miro[i]+ 1):
        if i + j < n:
            dp[i + j] = min(dp[i] + 1, dp[i + j])

if dp[-1] == 1000:
    print(-1)
else:
    print(dp[-1])

알고리즘:

dp를 이번에는 최대 값으로 지정해둔 뒤, (나는 걍 1000으로 설정) 차례대로 최솟값을 갱신해나가면 된다.

10
1 2 0 1 3 2 1 5 4 2

예시로 이렇게 있으면 dp는

[0, 1, 1000, 1000, 1000, 1000, 1000, 1000, 1000, 1000]
[0, 1, 2, 2, 1000, 1000, 1000, 1000, 1000, 1000]
[0, 1, 2, 2, 1000, 1000, 1000, 1000, 1000, 1000]
[0, 1, 2, 2, 3, 1000, 1000, 1000, 1000, 1000]
[0, 1, 2, 2, 3, 4, 4, 4, 1000, 1000]
[0, 1, 2, 2, 3, 4, 4, 4, 1000, 1000]
[0, 1, 2, 2, 3, 4, 4, 4, 1000, 1000]
[0, 1, 2, 2, 3, 4, 4, 4, 5, 5]
[0, 1, 2, 2, 3, 4, 4, 4, 5, 5]
[0, 1, 2, 2, 3, 4, 4, 4, 5, 5]

 

3 2 1 4 부분에서 예로 들어보면 i가 3일 때, dp는 [3, 4, 4, 4]로 갱신한 다음에, i가 2로 되면 dp의 4와 5를 비교해서 최솟 값으로 갱신해준다. 

----

이중 for문과 dp를 결합하다보니깐 혼란스러운 부분이 많았고, min을 사용할 경우 dp는 [0]으로 초기화 해주는 것이 아니라 maxsize나 테케에서 주어지는 가장 큰 값으로 지정하고 min 함수로 dp를 갱신해주어야겠다.

[Python] sys.maxsize - 최대 정수값