[코딩테스트 연습(Python)] 백준 2579번_계단 오르기(DP)

import sys

input = sys.stdin.readline

n = int(input())

# 계단의 점수를 저장. 1층 부터 저장한다.
stairs = [0] * 301
for i in range(1, n + 1):
    stairs[i] = int(input())

# 첫 번째 칸은 3칸 연속 밟을 수 없는 규칙에 해당하지 않음
dp = [0] * 301
dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

# 점화식을 계산
for i in range(4, n + 1):
	# 계단은 3칸 연속 오를 수 없음
    # 1. 현재 계단의 3칸 전까지의 dp값 + 한칸 전의 점수 + 현재 칸 점수
    # 2. 두칸 전 까지의 dp값 + 현재칸의 dp값
    # 1,2 중 더 큰 값을 dp[i]에 입력 
    # 이렇게 하면 3칸 연속 규칙을 지키며 최대값을 찾을 수 있다.
    dp[i] = max(dp[i - 3] + stairs[i - 1] , dp[i - 2]) + stairs[i]

print(dp[n])