[백준] 2579번 파이썬

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

문제 해결 방법

1. 문제의 조건처럼 계단 3개를 한번에 올라 갈 수 없고, 마지막 계단은 꼭 밟아야 한다. 계단이 4개라 가정했을 때 해당 조건을 만족하는 경우의 수는 주석과 같다.
2. 문제는 계단이 4개 미만일 때의 경우를 처리해줘야한다.

'''
패턴 확인
1 2 3 4
O X O O  => d[i] = stairs[i] + stairs[i - 1] + dp[i-3]
O O X O  => d[i] = stairs[i] + dp[i-2]
'''

import sys
input = sys.stdin.readline

N = int(input())
stairs = []
for n in range(N):
    stairs.append(int(input()))
dp = [0] * N

if N == 1:
    dp[0] = stairs[0]
if N == 2:
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
if N >= 3:
    dp[0] = stairs[0]
    dp[1] = stairs[0] + stairs[1]
    dp[2] = max(stairs[2] + stairs[1], stairs[2] + stairs[0])

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

print(dp[-1])