132. 2579(계단 오르기)

import sys
input = sys.stdin.readline

N = int(input())
stair = list(int(input()) for _ in range(N))
dp = []
try:
    dp.append(stair[0]) #dp[0]
    dp.append(max(stair[0]+stair[1], stair[1])) #dp[1]
    dp.append(max(stair[0]+stair[2], stair[1]+stair[2])) #dp[2]

    for i in range(3, N):
        dp.append(max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i]))
except:
    sum = 0
    for val in stair:
        sum += val
    dp.append(sum)

print(dp.pop())

문제요약

마지막 계단을 올랐을 때 최대값을 구하라.

조건 1. 연속 세개의 계단을 올라갈 수 없다.

조건 2. 마지막 계단은 반드시 밟아야 한다.

설명

그림으로 큰 틀은 이해가 될 것이다.

    dp.append(stair[0]) #dp[0]
    dp.append(max(stair[0]+stair[1], stair[1])) #dp[1]
    dp.append(max(stair[0]+stair[2], stair[1]+stair[2])) #dp[2]

 

어쩔 수 없이 dp[0],dp[1],dp[2] 는 따로 계산이 필요하다. 

dp.append(max(dp[i-3]+stair[i-1]+stair[i], dp[i-2]+stair[i]))

 

 

네번째 계단부터는 비교가 가능하다.

직전칸에서 올라온 경우와, 전전칸에서 올라온 경우를 따져 가장 큰 수를 더해나가면 된다.

의문점

 

1. 입력값이 7이 었다면?

dp에서는 각 계단별로 최댓값을 가지고 있다.

따라서 7에서 다시 위와 같은 식을 사용해서 계산을 할 수 있다.

 

2. 계산하는 계단의(dp) 최댓값이 직전칸에서 올라온 경우의 최댓값이었다면?

위와 같은 사고를 방지하기 위해서 dp[i-3] 혹은 dp[i-2]로 계산한다.

따라서 전 계단의 dp를 사용하지 않아 위와같은 오류가 나올 수가 없다.

 

주의점

계단수가 2칸까지 나올 수 있다.

따라서 이에 대한 처리가 따로 필요하다.

예외 처리를 통해 2칸일 경우는 따로 값을 받는 방법을 채택하였다.

 

[출처]https://daimhada.tistory.com/181