[백준 2579번] 계단 오르기 -python

문제 링크

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

2579번: 계단 오르기

풀이 

- dp 문제

- 앞으로 어떤 계단을 밟은 것인가 가 아니라 어떤 계단을 밟고 올라왔는가 라고 생각

- 바로 한칸 전 n-1 계단을 밟고 온 경우, 세 칸 연속 밟고 올 수 없으므로 그 이전 계단은 n-3계단 

- 두칸 전 n-2계단을 밟고 온 경우

- 점화식 

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

n = int(input())

data = []

for _ in range(n):
  data.append(int(input()))

if n == 1 :
  print(data[0])
else :

  dp = [0] * n 

  dp[0] = data[0]
  dp[1] = data[0] + data[1]

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

  print(dp[n-1])