[python] 백준 11060 점프 점프

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

11060번: 점프 점프

 

 

문제 해결

• 판에 써져 있는 수 이하만큼 이동을 해서 최소한의 이동으로 끝까지 가는 문제
• 사실 bfs를 쓰고 이동을 1~판에 써져 있는 수 로 해서 바로 끝냈지만 메모리가 초과 되었다.(아무래도 MAX 이동 가능 거리가 100이기 때문에 많은 경우의 수가 deque로 들어가는 경우가 있기 때문)
• 그래서 어떻게 조건을 주어서 que에 들어가는 양을 줄일까 생각을 했는데 DP였다.
• DP로 이미 그 지점을 지난 최소 경우의 수와 비교했을 때 더 크면 쓸모가 없기 때문에 버린다.
• 더 좋은점은 움직인 횟수를 dp에 저장하기 때문에 편하게 쓸 수 있다.

 

 

CODE

import sys
input = sys.stdin.readline
INF = sys.maxsize
from collections import deque
def bfs(num):
    global ans
    que = deque()
    que.append(num)
    dp[num] = 0
    while que:
        now = que.popleft()
        if now == n-1:
            ans = min(ans,dp[n-1])
        else:
            for i in range(1,A[now]+1):
                if now+i <n and dp[now+i] > dp[now]+1:
                    dp[now+i] = dp[now] + 1
                    que.append(now+i)
    
if __name__=='__main__':
    n = int(input())
    A = list(map(int, input().split()))
    dp = [INF]*(n)
    ans = INF
    bfs(0) # 거꾸로 계산
    print(ans if ans!=INF else -1)