[백준/python/2579]계단오르기

문제 링크: 계단오르기

처음 dp알고리즘을 배울 때 접했던 유형이 계단오르기였다. dp문제의 기본 문제라고 생각한다. 기본문제와 차이점은 한칸씩 밟는 것은 세 번 연속으로 할 수 없다는 점이다.

n=int(input())
stair=[0]*(301)
dp=[0]*(301)
for i in range(n):
    stair[i]=int(input())
dp[0]=stair[0]
dp[1]=stair[0]+stair[1]
dp[2]=max(stair[1]+stair[2],stair[0]+stair[2])
for i in range(3,n):
    dp[i]=max(dp[i-3]+stair[i-1]+stair[i],dp[i-2]+stair[i])
print(dp[n-1])

처음에는 stair와 dp배열의 크기를 n으로 뒀는데 런타임 에러가 떴다. 그래서 배열의 크기를 조정해서 해결했다.
마지막 계단을 기준으로 생각했을 때, 직전의 계단(i-1)을 밟았다면 그 이전에는 직전계단의 두칸 전의 계단(i-3)을 밟았을 것이고 직전의 계단을 밟지 않았다면 마지막 계단(i)와 두칸 전의 계단(i-2)를 밟았을 것이다.

말로 표현하려니 어려운 것 같다..공책에 그려가며 풀이하는 것을 추천한다.