[TIL] 백준 11060 - 점프 점프 ( python )

📌 문제 탐색하기

N : 배열의 크기 ( 1 ≤ N ≤ 1,000 )
A : 크기가 N인 배열 (0 ≤ Ai ≤ 100)

 

인덱스 i에 있는 숫자 A[i]는 최대 A[i]칸까지 오른쪽으로 점프 가능합니다.

시작점은 0번 인덱스이고, 도착점은 N-1번 인덱스이며,
가장 오른쪽 칸에 도달하기 위한 최소 첨프 횟수를 구하는 것이 핵심입니다.

 

가능한 시간복잡도

각 칸에서 가능한 점프 범위만큼 다음 칸들을 순회하면서 최소 점프 횟수를 갱신합니다.
이 과정에서, 각 칸에서 최대 A[i]번 반복하게 되며, 문제 조건에 따라 A[i]는 최대 100입니다.

• 외부 반복문은 0부터 N-1까지 순회하므로 O(N)
• 내부 반복문은 각 i마다 최대 A[i]번 수행하므로, O(A[i])
• 전체 시간복잡도는 O(N × K)이며, 여기서 K는 max(A[i])입니다.

최악의 경우에도 O(1000 × 100) = 100,000번의 연산이 발생하게 되며,
이는 제한 시간(1초 또는 2초) 안에 충분히 처리 가능합니다.

알고리즘 선택

각 칸까지 도달하는 최소 점프 수를 저장하고, 앞에서부터 순차적으로 갈 수 있는 칸들을 확인합니다.
기존 값보다 더 적은 점프로 도달할 수 있다면 dp[i] 값을 갱신하겠습니다.

---

📌 코드 설계하기

• 문제의 Input을 받습니다.
• 각 칸에 도달하는 최소 점프 횟수를 저장하기 위해 dp 배열을 생성하고, 모든 값을 무한대(float('inf'))로 초기화합니다.
• 시작점인 dp[0]은 0으로 초기화합니다. (0번 칸에서는 점프 없이 시작하므로 점프 횟수 0)
• 0번부터 N-1번까지 각 칸을 순회하며, 해당 칸에서 점프 가능한 범위만큼 다음 칸들에 대해 dp 값을 갱신합니다.
• dp[i]가 float('inf')가 아니라면, 현재 칸까지 도달이 가능하다는 의미입니다.
• i + 1부터 i + arr[i]까지 다음 칸들을 탐색합니다.
• 탐색 중 도달 가능한 인덱스가 범위를 초과하지 않으면, dp[j] = min(dp[i + j], dp[i] + 1)을 통해 최소 점프 횟수로 갱신합니다.
• 모든 과정을 마친 뒤, dp[N - 1]이 여전히 float('inf')인 경우는 도달 불가능으로 -1을 출력합니다.
• 도달 가능하다면 dp[N - 1] 출력 출력합니다.

---

📌 정답 코드

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * N

dp[0] = 0

for i in range(N):
    for j in range(1, A[i] + 1):
        if i + j < N:
            dp[i + j] = min(dp[i + j], dp[i] + 1)

if dp[N - 1] != float('inf'):
    print(dp[N - 1])
else:
    print(-1)