점프 점프 #11060

기억할 것

1. dp란 반복적으로 사용된 부분을 dp 배열에 저장하여 런타임을 줄이려는 알고리즘이다. 

2. dp는 dp배열을 사용하여 기록한다. 

이 문제에서 dp 배열이란, 각 위치까지 도달하는데 필요한 최소 점프 횟수를 저장하는 배열을 말한다. 

3. 변수가 2개이다 = for문을 2번 사용한다

이 문제에서는 기준 변수를 i, 목표 변수를 j로 잡음 

 

=> 중첩된 반복문에서 j는 현재 위치 i 이전의 위치를 나타낸다. j번째 위치에서 현재 위치 i로 도달할 수 있는 경우(즉, j + A[j] >= i), 최소 점프 횟수를 갱신한다. 

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

예제 입력 1 복사

10
1 2 0 1 3 2 1 5 4 2

예제 출력 1 복사

5

 

정답 코드 

#입력
n = int(input())
arr = list(map(int, input().split()))

#dp배열 제작 
dp = [n+1]*n #j번째에 도달하려면 최소 몇번 점프해야하는지를 쓴다 (점프가 안 되면 n+1로 기록될 것)
dp[0] = 0

for i in range(len(arr)):
    for j in range(1,len(arr)): #j는 목표 지점
        
        if arr[i] + i >= j: #미로의 i번째 칸에서 써있는 수 이내만큼 점프하여 도달할 수 있으면
            if dp[j] > dp[i] + 1:#그리고 그 점프가 기존 점프보다 작다면 
                dp[j] = dp[i] + 1#dp 배열 갱신
        else: 
            break #점프할 수 없으면 중단 

#출력 
if dp[-1] != n+1:
    print(dp[-1])
else:
    print(-1)

 

dp왜케어렵냐 ...