BOJ_2579_계단 오르기

DP(Dynamic Programming)의 전형적인 문제

항상 마지막 계단을 밟아야 하기 때문에 마지막 계단이 되는 dp[n]을 기점으로 생각해야 한다

계단은 두 칸 혹은 한 칸씩 올라갈 수 있는데, 연속해서 세 칸을 오를 수는 없기 때문에
dp[n]을 밟게 되는 경우는 2가지로 나뉜다

  1. n-3칸을 밟고 n-1칸을 밟은 후 n으로 오는 경우
  2. n-2칸을 밟고 n으로 오는 경우

따라서 점화식은 각각
dp[n] = dp[n-3] + stairs[n-1] + stairs[n]과
dp[n] = dp[n-2] + stairs[n]으로 나눠지며

max로 둘을 비교해서 더 큰 값을 넣어주면 된다

삽질

위의 점화식은 n이 4일 때부터 가능하기 때문에(점화식에 n-3이 있어서)
1부터 3까지는 수동으로 구해줘야 하는데
그 과정에서 n이 3보다 작을 경우를 생각하지 않았다

계단이 3칸보다 적게 있다면 나머지 칸을 0으로 만들어서 허수를 넣어주고 dp를 구하도록 코드를 수정했다

import sys  
  
n = int(input())  
stairs = [int(input()) for _ in range(n)]  
stairs.insert(0, 0) # 0 2 31 24  
  
if len(stairs) < 4:  
    remain = [0] * (4 - len(stairs))  
    stairs.extend(remain)  
  
dp = [sys.maxsize] * (n + 4)  
  
dp[1] = stairs[1]  
dp[2] = stairs[1] + stairs[2]  
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])  
  
for i in range(4, n + 1):  
    dp[i] = max(dp[i - 3] + stairs[i - 1], dp[i - 2]) + stairs[i]  
  
print(dp[n])