문제

풀이

먼저 이문제는
2번째 조건인 연속된 세 개의 계단을 모두 밟아서는 안된다고 한다.
i번째 계단까지의 합의 최댓값을 dp[i]라 했을 때

dp[i]는 무조건 2가지로 경우가 나뉘는데 i계단에 도착하기전에 i-1계단에서 1단점프를 하든가
아니면, i-2계단에서 2단점프를 하는 방법밖에없고
그런데 1단점프를 2번연속하면 규칙에 어긋나기 때문에
결국 i-1계단에서 1단점프를 했다면 i-3계단에서 2단점프후 1단점프를 한것이다.

따라서 점화식은
dp[i] = max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i]

코드

#점화식
#dp[i] = max(dp[i-2], dp[i-3] + step[i-1]) + step[i] 
import sys

N = int(input())

step = list()

for i in range(0, N):
  step.append(int(sys.stdin.readline().rstrip()))


dp = [0] * N
dp[0] = step[0]

if(N >= 3):
  dp[1] = step[0] + step[1]
  dp[2] = max(step[0], step[1]) + step[2]
  
  for i in range(3, N):
    dp[i] = max(dp[i-2], dp[i-3] + step[i-1]) + step[i]

  print(dp[N-1])
elif(N == 2):
  print(step[0] + step[1])

elif(N == 1):
  print(step[0])