[Python][백준/BOJ] 2579번 : 계단 오르기

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

2579번: 계단 오르기

 

내 코드

import sys
input = sys.stdin.readline

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

dp[1] = stair[1]
dp[2] = dp[1] + stair[2]

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

 

리뷰

2년만에 푼 문제다...ㅋㅋㅋㅋㅋ그리고 그 과정도 그렇게 순탄하진 않았다..

출력 초과는 출력값 보려고 써놓았던 것을 그대로 올려서 에러 처리 됐다고 쳐도, 런타임 에러가 자꾸 떠서 날 고통스럽게 했다.

그래서 300까지 자연수를 사용하는 것이 가능하다는 것을 이용해서, 301 최대치로 배열을 생성했다.

인덱스와의 투쟁은 그렇게 마무리되었다.

 

DP

문제를 보면, 이 문제에서는 계단이 나오고 조건은 계단이 3개 있을 때부터의 경우를 생각하게 한다.

당연히 계단이 2개까지 있는 경우는 2개를 다 밟는 것이 최댓값이다.

하지만 3개일 경우에는 3개를 연속으로 밟는 경우가 없도록 해야 하므로 DP를 사용해서 두 경우를 살펴봐야 한다.

밟는 계단이 (3개 전, 2개 전, 현재) VS (3개 전, 1개 전, 현재) 이렇게 된다.

이걸 DP를 통해 모든 경우를 살펴본 후 n번째의 dp를 출력하면 된다.