[백준] 2579 계단 오르기 (파이썬 python)

 

문제 링크

 

 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

 

문제

 

 

 

 

 

문제 풀이

 

 

전형적인 DP 방식으로 풀리는 문제이다.

주의해야 할 점은 현재 계단(i), 바로 아래 계단을 오를 경우 두 계단을 연속으로 올랐기 때문에

i - 3까지의 최댓값에 두 계단의 값을 더해야 한다는 점이다!

 

n = int(input())
array = [0] * 300
for i in range(n):
    array[i] = int(input())

dp = [0] * 300

dp[0] = array[0]
dp[1] = array[0] + array[1]
dp[2] = max(array[1] + array[2], dp[0] + array[2])

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

print(dp[n - 1])