[백준] 11060번 - 점프 점프 (Python)

문제

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

11060번: 점프 점프

 

접근 방법

동적 계획법 문제이다.

맨 오른쪽 칸부터 맨 왼쪽 칸 순서로 최소 점프 횟수를 구해나가면 된다.

맨 오른쪽 칸에서의 최소 점프 횟수는 0이고,

그 외 칸의 최소 점프 횟수는 그 칸에 적혀 있는 수가 N이라 했을 때, 그 다음칸 N개의 칸 중 최소 점프 횟수 + 1이다.

 

코드

N = int(input())
arr = list(map(int, input().split()))

INF = 10 ** 10
dp = [INF] * N # dp[i]는 i번째(i>=0)에서 끝 점까지의 최소 점프 횟수
dp[-1] = 0 # 끝 점은 점프를 하지 않고 바로 갈 수 있다.

for i in range(N - 2, -1 , -1):
    if arr[i] > 0:
        dp[i] = min(INF, min(dp[i+1:i+1+arr[i]]) + 1) # 다음 N칸 중 최소 점프 횟수 + 1칸 이동하면 끝 점으로 갈 수 있다.
        
if dp[0] == INF:
    print(-1)
else:
    print(dp[0])

 

풀이 정보

시도 횟수: 1회

총 문제 풀이에 걸린 시간: 7분 36초