[BOJ] Q2579 계단 오르기

[BOJ] Q2579 계단 오르기

Question

Language: Python

Difficulty: Silver 3

1번째 칸까지의 최대값은 1번째 계단(10)

2번째 칸까지의 최대값은 2번째(20) vs 1,2번째 계단(10+20)

3번째 칸까지의 최대값은 2,3번째 계단(20+15) vs 1,3번째 계단(10+20) ==> 2,3번째 계단

4번째 칸까지의 최대값은 1,3,4번째 계단(10+15+25) vs 1,2,4번째 계단(10+20+25) vs 2,4번째 계단(20+25)

5번째 칸까지의 최대값은 2,4,5번째 계단(20+25+10) vs 1,2,4,5번째 계단(10+20+25+10) vs 2,3,5번째 계단(20+15+10) vs 1,3,5번째 계단(10+20+10)

이렇게 보면 어느정도 규칙성이 보이는 것을 확인 할 수 있다.

5번째 계단을 오르는 경우를 자세히 보면

우선, 전단계에서 5번째 계단까지 올라올때 바로 전칸에서 올라올 수 있고, 전전칸에서 올라올 수 있다.

4번째 칸에서 올라오는 경우: 4->5을 거치게되는데, 그러면 연속된 두칸을 건너는 것이므로 3에서는 올라올 수 없고, 2에서 올라와서 4,5을 거쳐 5을 도착한다. 잘 보면, 2번째 이전의 경우는 이미 2번째 칸을 구하는 경우에서 최대값을 구해놓은 상황으로 더 이상 추가 연산을 하지 않아도 된다(memoization)

3번째 칸에서 올라오는 경우: 3->5을 거치므로 3이전의 경우도 살펴보면, 이미 3번째 칸을 확인하는 경우에서 최대값을 구해놓은 상태이다.

따라서 아래와 같은 점화식을 확인할 수 있다.

Algorithm

dp[i]=max(dp[i-3]+step[i-1]+step[i],dp[i-2]+step[i])

Solution

def solution():
    dp=[0] * (num+1) 
    dp[1]=stairs[1]
    
    if num==1:
        return dp[1]
    
    dp[2]=stairs[1]+stairs[2]
    
    if num==2:
        return dp[2]

    for i in range(3,num+1):
        dp[i]=max(dp[i-3]+stairs[i-1]+stairs[i],dp[i-2]+stairs[i])
        
    return dp[-1]
    
if __name__ =="__main__":
    num=int(input())
    stairs=[int(input()) for _ in range(num)]
    stairs.insert(0,0)
    print(solution())