[백준] 11060 : 점프 점프 / python

1. 문제 설명

11060번: 점프 점프

재환이가 1×N 크기의 미로에 갇혀있다.

미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다.

i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.

예를 들어, 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다.

이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오.

만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

입력

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

 

출력

재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다.

만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

 

2. 풀이 전 계획과 생각

• N → 미로의 크기
• Ai → Ai이하 만큼 오른쪽으로 떨어진 칸으로 한번에 점프할 수 있는 배열

 

• 예시
  10 1 2 0 1 3 2 1 5 4 2 5 ⇒ 1 + 2 + 1 + 3 + 2 ⇒ 5번
• 무조건 큰 것을 넣는다고 해서 오른쪽 끝에 도착할 수 없음으로 모든 경우를 따져봐야 한다.
  • 완전탐색으로 풀어본다면? 100^1000 ⇒ 시간 초과발생한다.
  • 오른쪽으로 가는 형태이니, 문제가 작아지는 형태이니 DP로 접근해보자.

 

• 풀고자 하는 문제는?
  dp[N] : N에 도착할 때, 최소 점프 횟수
• 점화식은?
  dp[current] current번 칸에 오기 전에 어디로 갈지 알 수가 없다.
  점프할 수 있는 모든 칸에 대해서 확인해야 한다.
  
  현재의 칸 : current
  다음 칸 : next_step
  
  current → current + next_step번으로 가려면,
  current + next_step ≤ A[current] 되어야 한다.
  
  dp[current+next_step] = min(dp[current]) + 1
  (1 ≤ next_step ≤ A[current])

• base 조건은?
  초기화 할때, -1로 초기화해준다.
  dp[0] = 0

 

3. 풀이

N = int(input())
arr = list(map(int, input().split()))
dp = [-1] * N
dp[0] = 0

for current in range(0, N-1):
    if dp[current] == -1:
        continue

    for next_step in range(1, arr[current] + 1):
        if current + next_step >= N:
            break
        if dp[current + next_step] == -1 or dp[current + next_step] > dp[current] + 1:
            dp[current + next_step] = dp[current] + 1

print(dp[N-1])

 

4. 풀이 후 알게된 개념과 소감

• 최소값을 갱신할 때, 최댓값으로 초기화하는 경우가 많았는데,
  불가능한 경우로 초기화하여 문제를 접근할 수 있다는 것을 알게 되었다.