[Code Tree] 최대 점프 횟수 [Python]

문제

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-maximum-number-of-jumps/description

 

 

---

풀이

문제 요약

각 요소의 수 arr[i]에 대해 1 ~ arr[i] 만큼 앞으로 건너뛸 수 있을 때 최대한 많이 점프하는 횟수를 구하자.

아이디어

점화식은 다음과 같다.

dp[i] : i번째 요소에서 1 ~ arr[i] 만큼 점프해서 갈 수 있는 최대 점프 횟수

주어진 배열의 반대부터 계산하면 쉽게 해결할 수 있다.

만약 arr[i]이 0보다 크면 1칸 이상 점프가 가능하다.

i + 1 부터 min(i + arr[i] + 1, n - 1)까지 점프 할 수 있으므로 이 중 최댓값을 찾아서 점프해주며 dp[0]까지 진행하자.

n = int(input())
arr = list(map(int, input().split()))

# Please write your code here.

dp = [0] * n
for i in range(n - 2, -1, -1):
    if arr[i] > 0:
        dp[i] = 1
    for j in range(i + 1, min(i + arr[i] + 1, n - 1)):
        dp[i] = max(dp[i], dp[j] + 1)

print(dp[0])

풀이시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/code-tree/Algorithm Intro/DP I/15 최대 점프 횟수(challenge-maximum-number-of-jumps).py

problem-solving/code-tree/Algorithm Intro/DP I/15 최대 점프 횟수(challenge-maximum-number-of-jumps).py at main · rogi-rog