[python] 백준 11060번: 점프 점프(DP)

#  11060 점프 점프

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

11060번: 점프 점프

⭐ 코드

import sys
input = sys.stdin.readline

N = int(input())
jump_list = 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, jump_list[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])

📝 풀이

1 2 0 1 3 2 1 5 4 2

오른쪽으로 길게 늘어진 배열에서 몇 번의 점프를 통해 끝에 도착하는지 구하는 문제이다.

각 인덱스에 해당하는 숫자 범위만큼 점프할 수 있다.

 

여기서 중요한 점이 무조건 큰 숫자를 넣는다고 해서 오른쪽 끝에 도착할 수 없다. 처음에는 숫자가 컸지만 그 다음 숫자가 작은 수(ex.0)일 수 있기 때문에 모든 경우를 따져봐야 한다.

🔓 정답 코드 뜯어보기

import sys
input = sys.stdin.readline

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

입력값을 각각 N과 jump_list에 담아주고 N의 크기만큼 dp를 생성해준다. 처음 출발하는 값은 0으로 체크해준다.

for current in range(0, N-1):
    if dp[current] == -1: # 1번
        continue
    
    for next_step in range(1, jump_list[current] + 1): # 2번
        if current + next_step >= N: # 3번
            break
        # dp = [0, 1, 2, 2, 3, 4, 4, 4, 5, 5]
        if dp[current + next_step] == -1 or dp[current + next_step] > dp[current] + 1: # 4번
            dp[current + next_step] = dp[current] + 1 # 5번

print(dp[N-1])

# 1번

만약 dp[current]가 방문하지 않은 곳이라면 건너뛰어준다. 처음에 dp[0] = 0으로 설정했기 때문에 아래 로직이 실행된다.

 

# 2번

jump_list의 인덱스 숫자만큼 next_step을 확인해준다. 

 

# 3번

만약에 current + next_step을 더한 값이 문제에서 주어진 N보다 크거나 같다면 범위를 벗어난 것이므로 break로 반복문을 통과시켜준다.

 

# 4번

dp[current + next_step]이 방문하지 않은 곳이거나 dp[current + next_step]이 dp[current] + 1 보다 크다면 다음 위치에 dp[current] + 1을 저장시켜준다. 그렇게되면 dp에 저장된 마지막 값이 오른쪽 끝 칸으로 가는 점프 횟수가 된다.