https://www.acmicpc.net/problem/2579
요즘 dp문제를 풀면서 따로 메모이제이션 하지 않고, 기존 데이터를 업데이트 하는 형식으로 바꾸어 풀고있다. 어차피 한번 한 계산은 다시 하지 않고, 이후의 계산에 기존 데이터가 필요하지 않다면 굳이 따로 기억할 필요가 없는 것 같다.
한번에 1개나 2개의 계단을 오를 수 있고, 연속된 계단을 최대 2개까지 오를 수 있다는 조건 때문에 기존 데이터에 가능한 경우의 수를 같이 가지고 있게 하였다.
탐색하고 있는 계단(i)은 반드시 선택한다는 가정하에 기존 계단의 점수를 그대로 초기화하였다. 각 계단의 첫 번째 숫자(i[0])는 직전 계단을 선택하지 않았을 경우의 최대값, 두 번째 숫자(i[1])는 직전 계단을 선택하였을 경우의 최댓값이다. 직전 계단을 선택할 경우에는 연속 계단을 최대 2개까지 오를 수 있는 것을 고려하여 탐색하고 있는 계단(i)을 업데이트 하였다.
이후 마지막 계단의 점수 중 더 큰 점수를 출력한다.
from sys import stdin
n = int(stdin.readline())
arr = [int(stdin.readline()) for _ in range(n)]
arr = list(map(list, zip(arr,arr)))
if n > 1: arr[1][1] += arr[0][0]
for i in range(2,n):
arr[i][0] += max(arr[i-2])
arr[i][1] += arr[i-1][0]
print(max(arr[-1]))
