[ 백준 2579 - 계단 오르기 ]

 

 

문제 푸는 아이디어

밑에서부터 올라갈 계단에 주목하는 것이 아니라, 계단에 올라와서 어느 계단에서 왔는지에 주목하자

 

① 한 칸 앞 계단에서 올라온 경우

dp(n) = stairs[n] + stairs[n-1] + dp(n-3)

 

② 두 칸 앞 계단에서 올라온 경우

dp(n) = stairs[n] + dp(n-2)

 

그리고 이 두 가지 경우 중 최댓값을 구하면 된다.

 

N = int(input())

stair = [0]
for _ in range(N):
    stair.append(int(input()))

if N == 1:
    print(stair[1])
else:
    dp = [0] * (N+1)
    dp[1] = stair[1]
    dp[2] = stair[1] + stair[2] 

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

    print(dp[N])