[실버 2] 백준 11060 - 점프 점프 (파이썬)

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

풀이

• 각 칸마다 점프할 수 있는 최대 칸 수가 주어짐
• 0번 인덱스부터 시작해서 N-1번 인덱스로 가야 함
• 최소 몇 번의 점프로 도달할 수 있는지 구함
• 못 가면 -1 출력

N = int(input())  # 칸의 수
A = list(map(int ,input().split()))  # 각 칸에서 점프 가능한 최대 거리

A[i]는 i번 칸에서 최대 A[i]칸 까지 점프가 가능하다는 뜻을 의미한다.

D = [1e9] * N  # DP 배열, 최소 점프 횟수를 저장 (초기값은 매우 큰 값)
D[N - 1] = 0   # 마지막 칸은 도달했으므로 점프 횟수 0

for i in range(N - 2, -1, -1):  # 뒤에서부터 탐색
    for j in range(1, A[i] + 1):  # 점프 가능한 거리만큼
        if i + j >= N:
            break  # 범위 넘어가면 종료
        D[i] = min(D[i], 1 + D[i + j])  # 다음 칸까지 최소 점프 갱신

뒤에서 부터 역방향으로 최솟값을 갱신한다.

예를 들어서 입력값이 다음과 같다.

6
2 0 1 0 1 0

• 0번에서 최대 2칸 점프 가능 → 1번 or 2번 이동 가능
• 1번은 0 → 이동 불가
• 2번은 1칸 → 3번 이동 가능
• 3번은 0 → 이동 불가
• 4번은 1칸 → 5번 이동 가능
• 5번은 0 → 마지막 칸 도달

코드

# 백준 11060 - 점프 점프
# 분류 : 다이나믹 프로그래밍

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

D = [1e9] * N
D[N - 1] = 0
for i in range(N - 2, -1, -1) :
    D[i] = 1e9
    for j in range(1, A[i] + 1) :
        if i + j >= N :
            break

        D[i] = min(D[i], 1 + D[i + j])

if D[0] == 1e9 :
    print(-1)
else :
    print(D[0])