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

---

문제 파악

계단을 올라가며 방문한 계단에 모든 값들을 더했을 때 값이 최대여야 한다.

단 올라갈 때 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

---

dp[n] = n칸 까지 도달할때 까지의 최댓값

dp[n]의 점화식을 구해야 한다.

dp문제는 원인 -> 결과 로 생각하기보다는
결과지점부터 역으로 생각을 하며 어떻게 이 결과를 도출할지를 생각하는 것이 조금 더 수월한 방법이라고 생각된다.

1) n번째 계단을 밟을 때 그 전단계는 n-1 또는 n-2 둘 중 하나다.

2-1) 그 중 n-1을 밟고 오는경우에는 또 그전에 n-2는 밟으면 안 된다 (연속 3칸 금지 때문)
2-2) 그래서 그 n-1은 그전에 n-3에서 왔다고 보면 된다.

3) n-2를 밟고 오는 경우는 그전에 뭘 밟고 오든 상관 없다.

---

n-1번째 계단으로 오는 경우에는
dp[n] = dp[n-3] + stairs[n-1] + stairs[n]

n-2번째 계단으로 오는 경우에는
dp[n] = dp[n-2] + stairs[n]

---

해답 및 풀이

import sys
input = sys.stdin.readline

N = int(input())

# DP 설정
stairs = [0] * 301
for i in range(1,N+1):
    stairs[i] = int(input())

dp = [0] * 301

dp[1] = stairs[1]
dp[2] = stairs[1] + stairs[2] 

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

print(dp[N])

dp문제는 거꾸로 결과에서 거슬러 올라가보는 습관 가져보기