[백준, 2579번] 계단 오르기

생각하는 핵심

• DP로 접근할 때는 항상 최댓값을 끝까지 올려준다는 생각을 해줘야 할 듯.
• 물론 규칙을 적용한 상태로!
• 해당 문제의 규칙으로는
  • 연달아서 3 칸의 계단을 접근하지 못한다는 것.
  • 최대 2 칸만 건너뛸 수 있다는 점.
• 아래 문제에서 계속 혼동스러웠던 점
  • dp에 넣어주는 값이 위의 규칙을 잘 지켜가며 올라가는 것인지에 대한 점.
    • 이유는 해당 계단에서 두 칸을 모두 밟으며 올라간 값이 최댓값이어서 dp에 넣고
    • 그 다음 계단에서도 두 칸을 모두 밟으며 올라간 값이 최댓값이어서 dp에 넣게 된다면
    • 연속해서 계속 계단을 밟아가는 것이 아닐까? 라는 생각으로 엄청 혼동스러웠음...
  • 그래서 stairs와 dp를 구분해서 생각을 해본다면 조금은 이해가 갈 것이라고 생각한다.
  • 단순히 더해지는 stairs의 값과 지금까지 중첩해온 최댓값인 dp를 구분하기!

import sys
input = sys.stdin.readline
n = int(input())
stairs = [int(input()) for _ in range(n)]
if n <= 2:
    print(sum(stairs))
else:
    dp = [stairs[0]]+[stairs[0]+stairs[1]]+[0]*(n-2)
    for i in range(2, n):
        dp[i] = max(stairs[i]+stairs[i-1]+dp[i-3], stairs[i]+dp[i-2])
    print(dp[-1])