[백준] 2579번 계단 오르기

https://www.acmicpc.net/problem/2579

다이나믹 프로그래밍으로 풀기 위해 점화식을 세우는 것이 힘들어 구글링을 통해 일부 해결하였다.

i - 2 계단 밟는 경우와 i - 3 계단 밟는 경우로 나뉘는 것은 알았는데, 그 이후 코드를 어떻게 짜야할 지 감이 안와서 어려움을 겪었던 문제였다. 다이나믹 프로그래밍 문제들을 반복해서 풀면 조금 나아질 것 같다..!

계단 값 저장하는 리스트를 계속 n개로 저장해서 런타임 에러가 발생했었다 😭

# 2579 : 계단 오르기

import sys
imput = sys.stdin.readline

n = int(input())
# 계단 값 저장하는 리스트 n개로 저장하면 런타임에러(인덱스에러) 발생
stair = [0] * 301

for i in range(n):
    stair[i] = int(input())

# dp 테이블 초기화
d = [0] * 301

d[0] = stair[0]
d[1] = max(stair[0] + stair[1], stair[1])
d[2] = max(stair[0] + stair[2], stair[1] + stair[2])

# 마지막 계단을 밟아야 하므로 
# i - 2 계단 밟는 경우와 i - 3 계단 밟는 경우로 나뉨
for i in range(3, n):
    d[i] = max(d[i - 2] + stair[i], d[i - 3] + stair[i - 1] + stair[i])

print(d[n - 1])

Uploaded by Notion2Tistory v1.1.0