[백준(Python)] 2579번 : 계단 오르기

문제

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

2579번: 계단 오르기

---

코드

import sys
input = sys.stdin.readline

n=int(input()) # 계단 개수
s=[int(input()) for _ in range(n)] # 계단 점수 리스트
dp=[0]*n

if len(s)<=2:   # 계단 두 개 이하일 때,
    print(sum(s))   # 그냥 모두 더함.
else:
    dp[0] = s[0]
    dp[1] = s[0]+s[1]
    for i in range(2,n):
        dp[i]=max(dp[i-3]+s[i-1]+s[i], dp[i-2]+s[i])
    print(dp[-1])

---

해설

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

• dp[i - 3] + s[i - 1] + s[i]
  • i-3번째 계단에서 2칸을 뛰어서 i번째 계단에 도착
• dp[i - 2] + s[i]
  • i-2번째 계단에서 1칸을 뛰어서 i번째 계단 도착