[BOJ] 11060 점프 점프

1~1000 사이의 n입력받아 길이가 n인 배열을 입력받는다.

한 번에 이동할 수 있는 거리는 0~100 사이의 값이고 1부터 1000까지 최대 이동 횟수는 999회. 

각 위치에 해당하는 최소 이동횟수를 저장시켜야 함 -> DP 문제일 것.

입력도 작고 이동 거리도 작으므로 그냥 BFS로 다 넣어서 풀어도 풀리긴 할 것?

 

 

bfs 풀이

 

쓸데없는 곳까지 굳이 탐색하여 시간효율도 별로고

배열도 써서 메모리 효율도 별로일 듯..

 dp로 예상됨.
# 뒤로 가는거 없음.
# bfs? 로 풀 수 있을 듯?

import sys
from collections import deque
input=sys.stdin.readline

n=int(input())
arr=list(map(int,input().split()))
visited=[0]+[1000 for i in range(n-1)] # 1번째는 무조건 0,

def jump():
    queue=deque([[arr[0],0,0]]) # arr[0]번째 값(이동가능거리),현재위치,현재이동횟수
    while queue:
        can,idx,tmpt=queue.popleft()
        for i in range(1,can+1): # 이동 가능 거리만큼 반복
            if idx+i<n: # n까지 이므로, 범위 밖으로 안나가게
                if tmpt+1<visited[idx+i]:
                    visited[idx+i]=tmpt+1
                    queue.append([arr[idx++i],idx+i,tmpt+1])
jump()
print(visited[-1] if visited[-1]!=1000 else -1)

dp 풀이

 

dp안에 저장되어있는 현위치로부터 j+1칸 떨어져있는 곳의 값과

dp안에 저장되어있는 현위치+1한 값중 작은 값을 

dp [현위치로부터 j+1칸 떨어져있는 값]에 저장

from sys import stdin
input=stdin.readline

n=int(input())
arr=list(map(int,input().split()))
dp=[0]+[1000 for i in range(n-1)] # 1번째는 무조건 0

for idx,i in enumerate(arr): # arr의 길이만큼 반복,
    for j in range(i):
        if idx+j+1<n:
            dp[idx+j+1]=min(dp[idx]+1,dp[idx+j+1])
            # dp안에 저장되어있는 현위치로부터 j+1칸 떨어져있는 곳의 값과
            # dp안에 저장되어있는 현위치+1한 값중 작은 값을
            # dp [현위치로부터 j+1칸 떨어져있는 값]에 저장

print(dp[-1] if dp[-1]!=1000 else -1)
# 만약 dp의 맨 끝의 값이 1000이 아니면 그 값 출력, 1000이면 -1 출력