백준 2579번 - 계단 오르기 파이썬

📌 백준 2579번 - 계단 오르기 (DP)

✨ 문제 요약

각 계단에는 점수가 주어지고, 계단을 밟으면 그 점수를 얻게 됩니다.
다음 조건을 지키면서 마지막 계단까지 올라가며 얻을 수 있는 최대 점수를 구하는 문제입니다.

조건

• 한 번에 1칸 또는 2칸씩 오를 수 있다
• 연속된 3개의 계단을 밟을 수 없다
• 마지막 계단은 반드시 밟아야 한다

---

🧠 문제 해석

이 문제는 최댓값을 구하는 DP 문제입니다.
특히, 연속 세 계단 금지라는 제약 때문에 두 가지 경로만 고려할 수 있습니다:

✅ i번째 계단을 밟는 두 가지 방법

1. i-2 → i
   → 두 칸 점프 → dp[i-2] + arr[i]
2. i-3 → i-1 → i
   → 한 칸, 한 칸 → dp[i-3] + arr[i-1] + arr[i]

그래서 점화식은 다음과 같습니다:

dp[i] = max(
    dp[i-2] + arr[i],
    dp[i-3] + arr[i-1] + arr[i]
)

---

🧱 DP 테이블 구성 (초기값 중요!)

i	dp[i]	의미
0	arr[0]	첫 계단은 무조건 밟음
1	arr[0] + arr[1]	두 번째 계단은 연속 두 칸 가능
2	max(arr[0]+arr[2], arr[1]+arr[2])	세 번째는 연속 두 칸 or 한 칸 건너

---

✅ 정답 코드 (Python)

N = int(input())
arr = [int(input()) for _ in range(N)]

if N == 1:
    print(arr[0])
elif N == 2:
    print(arr[0] + arr[1])
else:
    dp = [0] * N
    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    dp[2] = max(arr[0] + arr[2], arr[1] + arr[2])

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

    print(dp[N - 1])

---

🧩 배운 점

• DP 문제는 점화식 설계보다 조건 정리가 먼저다
• 연속 세 계단 금지 조건 때문에 두 가지 경로만 고려
• 마지막 계단은 반드시 밟아야 하므로, dp[N-1]이 정답
• 초기값 설정(dp[0], dp[1], dp[2])이 문제의 절반이다

---

🎓 정리

항목	설명
문제 유형	DP (최댓값)
핵심 점화식	dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])
초기값	dp[0] = arr[0], dp[1] = arr[0]+arr[1], dp[2] = max(arr[0]+arr[2], arr[1]+arr[2])
주의	마지막 계단은 반드시 밟아야 함

---

🏷 해시태그

#DP #계단오르기 #백준2579
#최대점수 #점화식 #파이썬DP
#백준Python #알고리즘공부

```