[DP] 계단 오르기

개구리가 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 점프하는 게임을 하려고 한다.
개구리는 한 계단을 점프해서 오를 수도 있고, 두 계단을 점프해서 오를 수도 있다.
각 계단에는 일정한 점수가 부여되어 있으므로, 개구리가 계단을 밟으면 그 계단의 점수를 획득한다.
예를 들어, 아래 그램에서 개구리가, 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면
개구리가 획득하는 점수는 10 + 20 + 25 + 20 = 75점이 된다.

N개의 계단에 부여된 점수가 주어질 때, 개구리가 획득할 수 있는 최대 점수를 출력하시오.

Input
첫째 줄에 계단의 개수 N이 주어진다.
둘째 줄에 N개의 계단의 점수가 차례대로 주어진다.
6
10 20 15 25 10 20

6
10 -20 -15 25 -10 20

6
-10 -20 15 25 -10 -20

Output
첫째 줄에 계단 오르기 게임으로 얻을 수 있는 최대 점수를 출력한다.
100

40

10

import sys
input=sys.stdin.readline

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

dp=[0]*(n) # dp table 생성 -> 개구리가 획득할 수 있는 최대 점수
dp[0]=step[0] # 1번 계단을 오르는 경우는 한가지
dp[1]=max(step[0]+step[1], step[1]) # 2번 계단을 오르는 경우: 한칸+한칸 or 두칸
for i in range(2, n):
    dp[i]=step[i]+max(dp[i-1], dp[i-2]) # 현재 계단의 점수 + 개구리가 획득할 수 있는 점수의 최대


print(dp[n-1]) # 마지막 계단에 오를때 최대값

 

 

개구리는 한칸 or 두칸을 이동할 수 있으므로 ..

i번째 계단에 도달할 수 있는 경우의 수는?

[1] i-1에서 i계단으로 한칸 이동하기

[2] i-2에서 i계단으로 두칸 이동하기

 

비슷한 문제
https://www.acmicpc.net/problem/2579

import sys

n=int(sys.stdin.readline()) #계단 수

#계단의 점수
step=[0]*(n+2)
for i in range(0, n):
    step[i]=int(sys.stdin.readline())

dp=[0]*(n+2)
dp[0]=step[0] 
dp[1]=step[0]+step[1]
dp[2]=max(step[0]+step[2], step[1]+step[2])

for i in range(3, n):
    dp[i]=max(dp[i-3]+step[i-1]+step[i], dp[i-2]+step[i])    

print(dp[n-1])​

 

 

 

 

---

경로를 출력하고 싶으면..

# 계단의 경로를 출력
n = int(input())

arr = list(map(int, input().split()))
arr.insert(0,0)

dp = [0]*(n+1)
check = [0]*(n+1)
dp[1]=arr[1]

for i in range(2, n+1) :
    dp[i] = max(dp[i-1], dp[i-2])+arr[i]
    #arr[i] += max(arr[i-1], arr[i-2])

    if dp[i-1] > dp[i-2] :
        check[i]=1
    else :
        check[i]=2

#print(arr[n])
#print(arr)
print(dp)
print("jump 수 : ", end= ' ')
print(*check)
print('경로 역순 : ')

while(n!=1) :
    print(n, arr[n])

    if check[n]==1 :
        n-=1
    else :
        n-=2

print(n, arr[n])