📌 문제 요약

• 문제 이름: 2579번: 계단 오르기
• 알고리즘 분류: 다이나믹 프로그래밍 (DP)
• 사용 언어: Python 3

각 계단에 쓰여 있는 점수가 주어질 때, 규칙을 만족하면서 꼭대기 계단까지 올라갔을 때 얻을 수 있는 점수의 최댓값을 구하는 문제입니다.
핵심 규칙은 "연속된 세 개의 계단을 모두 밟아서는 안 된다"는 것과, "마지막 도착 계단은 반드시 밟아야 한다"는 것입니다.

---

💡 문제 접근 방법 (핵심 로직)

이 문제는 이전 단계의 최적해가 다음 단계의 최적해를 구하는 데 사용되는 전형적인 동적 계획법(DP) 문제입니다. 가장 중요한 것은 '연속된 3계단을 밟을 수 없다'는 제약 조건을 점화식(Recurrence Relation)으로 어떻게 표현하느냐입니다.

마지막 $i$번째 계단에 도착하기 위한 경우의 수는 딱 두 가지뿐입니다.

1. 전전 계단($i-2$)에서 2칸을 뛰어 올라온 경우: - 이 경우에는 전전 계단에 도달할 때의 누적 최댓값(dp[i-2])에 현재 계단의 점수(stairs[i])를 더해주면 됩니다.
   • 식: dp[i-2] + stairs[i]
2. 바로 직전 계단($i-1$)에서 1칸을 올라온 경우:
   • 이 경우가 중요합니다. 직전 계단에서 올라왔다면, 그 직전 계단은 절대로 그 전전 계단($i-2$)에서 1칸 올라온 것이어선 안 됩니다. (그러면 3연속 밟기가 되므로)
   • 즉, 무조건 3칸 전 계단($i-3$)에서 2칸을 뛰어 $i-1$로 온 상태여야 합니다.
   • 식: dp[i-3] + stairs[i-1] + stairs[i]

이 두 가지 경우 중 더 큰 값을 선택하는 것이 이 문제의 점화식이 됩니다.

$DP[i] = \max(DP[i-2] + stairs[i], DP[i-3] + stairs[i-1] + stairs[i])$

---

💻 코드 구현

import sys
input = sys.stdin.readline

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

dp = [0] * 301

dp[1] = stairs[1]
if N >= 2:
    dp[2] = stairs[1] + stairs[2]
if N >= 3:
    dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

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

---

🚨 트러블 슈팅 및 회고

• 런타임 에러(IndexError) 방지 전략: 처음에 stairs와 dp 배열의 크기를 입력받은 N의 크기만큼만 할당([0] * (N + 1))하는 방식을 고민했습니다. 하지만 이 경우 $N$이 1이나 2처럼 작게 주어졌을 때, dp[3]을 초기화하는 과정에서 인덱스 에러가 발생하게 됩니다. 이를 해결하기 위해 문제 조건의 최댓값인 300을 기준으로 크기가 301인 배열을 미리 선언하여 공간을 고정해 두고 풀이했습니다. 메모리를 미세하게 더 쓰더라도 배열 참조 에러를 원천 차단하는 매우 안정적인 방식임을 배웠습니다.
• Top-Down vs Bottom-Up: 재귀를 사용하는 탑다운 방식도 가능하지만, 파이썬의 재귀 깊이 제한을 고려하고 반복문을 통한 바텀업(Bottom-Up) 방식으로 구현하여 $O(N)$의 시간 복잡도로 안전하고 빠르게 통과했습니다.