[BOJ/Python] 백준 11060번 - 점프 점프

백준 #11060 점프 점프

11060번: 점프 점프

import sys
input = sys.stdin.readline

n = int(input())
maze = list(map(int, input().split()))
dp = [sys.maxsize for _ in range(n)]

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

if dp[-1] == sys.maxsize:
  print(-1)
else:
  print(dp[-1])

dp 리스트에는 해당 칸에 오기까지 점프하는 횟수의 최솟값이 저장된다. 따라서 리스트 각 요소는 최대 사이즈 값으로 초기화해주고, 0번째 요소는 0으로 초기화해준다. (0번째 칸은 점프를 하지 않은 맨처음 시작 위치)

현재 위치에서 점프하여 갈 수 있는 모든 칸을 계산하여 해당 위치의 점프 횟수를 더 작은 것으로 갱신해준다.

 

현재 위치에서 점프하여 갈 수 있는 칸의 최소 점프 횟수 = min(기존 값, 현재 위치까지 오는 데 최소 점프 횟수 + 1)