[백준] 2579 (실버3)

문제는 다음과 같고, 시간 제한과 메모리 제한은 각각 1초와 128 MB이다.

대표적인 다이나믹 프로그래밍 문제이다.
dp 테이블에는 해당 계단을 무조건 밟는 경우의 값을 기록할 것이다.
따라서 dp[0]는 0번째 계단의 점수가 된다.
dp[1]은 0번째와 1번째를 모두 밟는 경우이다.
dp[2]는 0번째와 2번째를 밟거나, 1번째와 2번째를 밟는 경우 중 max 값을 가진다.
즉, dp[i]는 i-2번째와 i번째를 밟는 경우와 i-3번째와 i-1번째, 그리고 i번째를 밟는 경우 중 max 값을 가진다.

n = int(input())

steps = []
for _ in range(n):
    steps.append(int(input()))
# 해당 계단을 무조건 밟는 경우의 값 기록
dp = [0] * (n+1)
# 첫번째 계단 밟는 경우
dp[0] = steps[0]
# 두번째 계단 밟는 경우
dp[1] = steps[0] + steps[1]
# 세번째 계단 밟는 경우
dp[2] = max(steps[0] + steps[2], steps[1] + steps[2])

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

print(dp[n-1])