[BOJ 2579] 계단 오르기(Python)

문제링크

계단 오르기

풀이 전 계획 및 생각

연속된 세 개의 계단을 모두 밟아서는 안된다는 조건과 한 번에 한 계단 또는 두 계단씩 오를 수 있다는 조건에서 점화식을 만들 수 있었다.
dp배열에는 i-1번째(인덱스가 0부터 시작)을 밟았을 때, 얻을 수 있는 가장 큰 점수를 저장하도록 했다.
i번째 계단을 밟을 수 있는 경우는 i-2번째 계단에서 2칸을 오른 경우와 i-3번째 계단에서 i-1번째 계단과 현재의 계단을 밟은 경우다. i-1번째가 아닌 i-3번쨰 계단을 고려한 이유는 i-1번째를 보면 연속 3개를 밟았는지 아닌지를 구분해낼 수 없다고 생각했기 때문이다.
그래서 최종적으로 얻어낸 식은
dp[i] = max(dp[i-2]+stair[i],stair[i-1]+stair[i]+dp[i-3])
이다.

풀이

import sys

stair = [0]*301
dp = [0]*301

n = int(sys.stdin.readline())

for i in range(n):
    stair[i] = int(sys.stdin.readline())

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

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

풀이하면서 막혔던 점과 고민했던 점

처음에 i-3번째 계단까지 고려하는 것이 아닌 i-2번째와 i-1번째 계단만 고려했을 때, 문제가 잘 풀리지않았다. 그래서 규칙성을 찾기위한 범위를 넓혀보았고, 덕분에 찾을 수 있었다.

풀이 후 알게된 개념과 소감

DP인 것 같은데 못 풀겠으면, 살펴볼 영역을 조금 넓혀봐야겠다는 생각을 했다.