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

0. 문제 링크

 

 

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

11060번: 점프 점프

---

1. 풀이 방법

 

 

i에서 j로 가는데, 기존에 점프한 횟수보다 i + 1이 더 적으면 가면 된다.

dp 배열은 inf로 초기화 해야 한다.

이런 식으로 모든 i에 대해서, 점프할 수 있는 j를 찾아가며 초기화를 하면 결국 최소 횟수가 나오게 된다.

---

2. 코드

 

 

import sys

n = int(sys.stdin.readline().strip())
board = [b for b in map(int, sys.stdin.readline().split())]
dp = [float('inf')] * n
dp[0] = 0
for i in range(n):
    for j in range(1, board[i] + 1):        # board[i]에 있는 숫자만큼 점프할 수 있음
        if i + j < n:       # 범위를 벗어나지 않는다면
            dp[i + j] = min(dp[i + j], dp[i] + 1)       # i + j까지 가는데 기존에 점프한 횟수와 dp[i]에서 한 번 점프하는 것을 비교

if dp[n - 1] == float('inf'):
    print(-1)
else:
    print(dp[n - 1])

---

3. 마무리