2579번 계단 오르기

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

처음으로 DP 알고리즘을 이용해서 풀어본 문제. 이제는 DP를 자주 이용하고 가장 먼저 떠오른다.

사고 과정

예전에는 어떻게 생각했나 몰라. 지금이라면 조건에 맞춰서 문제를 해부, 정리.
1. 다음칸 OR 다다음칸
2. 연속된 3개 X. 즉, 다음칸을 밟으면 무조건 다다음칸.
3. 마지막 도착 계단은 무조건 밟아야 한다. 그러면 마지막칸을 기준으로 생각하자. 거꾸로!

마지막 칸(N)은 그러면 (N-1)이나 (N-2)로 부터 귀결되겠지. 조건 때문에 N-1 에서 오면 부가적으로 조건이 붙는다... ( N-3번째 계단을 밟고 와야해 )
N은 그러면 "N-1번째 계단을 밟았을 때"와 N-2번째 계단을 밟았을 때" 중 더 큰 것을 밟고 오겠지. 계단의 값과 별도로 i번째 계단을 밟았을 때 가질수 있는 최댓값을 memorization한 list를 따로 만들자... 이것이 DP의 특징

*결국 답으로 귀결될 수 밖에 없는 구조, 수식으로 작성

import sys

N = int(sys.stdin.readline().rstrip("\n"))
stair=[0]+[int(sys.stdin.readline().rstrip("\n")) for _ in range(N)]
dp = [0 for _ in range(N+1)]
for n in range(1,3) :
    dp[n]=stair[n]+stair[n-1]
    if N==1 : break

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

좀 더 날카롭게 하고 싶은데 이게 한계인가...