[백준/2579/파이썬] 계단오르기

---

소스코드

N = int(input())

s = []

for i in range (N):

  s.append(int(input()))

dp = [0]* (N)

dp[0] = s[0]

dp[1] = s[0]+s[1]

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

for i in range(3,N):

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

print(dp[N-1])

---

알고리즘

계단을 오르는 방법은 2가지가 있다.

1. 연속된 2계단 오르고 2칸 오르기

2. 한칸 밟고 1칸 밟기

이해를 돕기 위해  마지막 계단을 생각해보면

 

1. 마지막 계단(N)은 밟아야한다.

2-1. N-1을 밟으면 N-3에서 올라와야한다(연속된 3개는 못 오르므로)

2-2. N-2를 밟으면 N으로 가면 된다.

이 부분이 위의 설명을 나타낸 코드이다.

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