[BOJ] [Python] 2579번 : 계단 오르기

어느 계단이든지, 그 계단을 밟기 위한 방법은 2가지이다.

 

n번째 계단을 예시로 생각해보자.

 

 

1. n-2번째와 n번째 밟기

 

방법 1

 

 

2. n-3번째와 n-1번째, n번째 밟기

 

방법 2

 

첫 번째 방법에서는 n-2번째 계단이,

두 번째 방법에서는 n-3번째 계단이 첫 계단이다.

 

이 계단들은 그 자리에 오기까지의 값을 dp 리스트에 저장하고 있어야 하고, 

계산할 때, 계단의 값이 아닌 dp 값을 더해야 한다.

 

 

방법1과 방법2 중 더 큰 값을 골라,  n번째 dp에 저장한다.

 

num = int(input())

li = [0]
dp = [0] * (num + 1)

for n in range(num):
    li.append(int(input()))

for i in range(1, num+1):
    if(i == 1):
        dp[1] = li[1]

    elif(i == 2):
        dp[2] = li[1] + li[2]

    else: # i >= 3
        dp[i] = max(dp[i-2] + li[i], dp[i-3] + li[i-1] + li[i])

print(dp[num])