[백준] 2579. 계단 오르기 | 파이썬

백준 2579. 계단 오르기 - 실버III

문제 설명

계단 규칙
1. 한번에 1개 or 2개
2. 연속된 3개 밟을 수 없음. 단, 시작 계단 포함 X
3. 마지막 계단 꼭 밟기

⟹ 점수 최대값? 

---

 

* 주의 1

처음 3칸에 대한 초기화 먼저 해야함! (계단이 3개 밖에 없을 경우 고려!)

dp[1]의 최대 → 그냥 계단 1칸
dp[2]의 최대 → 계단 1칸 + 계단 2칸
dp[3]의 최대 → max(③ + ②, ③ + ①)

 

* 주의 2

이 문제는 계단의 크기가 한정되어 있었음(301개 최대)! 그래서 리스트의 크기를 N개(실제론 (n+1)로 구현)로 설정하면 런타임에러가 뜸!

→ 301이 더 작으니깐 주어진 조건 그냥 쓰자~

---

파이썬 코드

N = int(input())
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]
dp[3] = max(stairs[1] + stairs[3], stairs[2] + stairs[3])

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

print(dp[N])