[백준/Python] #25706 자전거 묘기

문제

알고리즘

출발한 칸에 따라서 총 몇개의 칸을 밟는지 계산하는 문제이다.

내가 i번째 칸에서 시작했다고 했을때, i+k 번째 칸을 밟는다고 가정하면 i번째 칸에서 i+k번째 칸으로 갈때까지 밟는 칸수와 i+k에서시작했을때 밟는 칸수의 합이 답이 되므로 역순으로 계산하면 편리하겠다고 생각했다.

예시를 확인하면

9에서 시작하면 9만 밟게 되므로 1칸

8에서 시작하면 8만 밟게 되므로 1칸, 8 + 3은 N = 9인 경우를 넘어가버리므로 제외한다.

7에서 시작하면 7, 8을 밟게 되므로 2칸, 7에서 8로 갈때 1칸을 밟고 8에서 시작한 경우 +1 해서 2칸이다.

6에서 시작하면 6,7,8을 밟게 되므로 3칸, 6에서 7로 갈때 1칸을 밟고 7에서 시작한 경우 +2해서 3칸이다.

5에서 시작하면 5,7,8을 밟게 되므로 3칸, 5에서 7로갈때 1칸을 밟고 7에서 시작한 경우 +2해서 3칸이다.

...

이렇게 DP를 역순으로 계산해나가면 된다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))
dp = [0] * (n + 2)

for i in range(n, 0, -1):
    jump = arr[i - 1]
    next = i + jump + 1
    if next > n:
        dp[i] = 1
    else:
        dp[i] = dp[next] + 1

print(' '.join(map(str, dp[1:n+1])))

현재칸에 점프대가 있는지 여부를 검사한 뒤에, 해당 칸에서 이동할 수 있는 칸의 DP배열을 확인해서 DP배열을 계속 업데이트해주면 된다.