[알고리즘] 계단 오르기

문제 기술

n(1이상 20이하 정수)개 계단을 바닥에서 위로 올라가려고 한다. 계단을 올라갈 때 한 번에 1개, 3개 혹은 4개의 계단만 오를 수 있다. 바닥에서 가장 위의 계단으로 올라갈 때, 올라가는 방법의 수를 구하는 프로그램을 작성하시오.

입력 형식

첫 번째 줄에 양의 정수 n이 주어진다.

출력

바닥에서 가장 위의 계단으로 올라가는 방법의 수를 출력한다.

입력 예 및 출력 예

8 // 25

나의 코드

import sys

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

def dpstair(n):
   C = [0 for i in range(n+1)]
   C[0] = C[1] = C[2] = 1
   C[3] = 2
   for i in range(4, n+1):
       C[i] = C[i-1] + C[i-3] + C[i-4]
   return C[n]

print(dpstair(n))

아주 기본적인 동적계획법 개념 문제이다. C[0]은 0으로 고정이 되어있어야 하고, 3번째까지는 직접 구해야 한다.
4번째부터, 전체를 오르는 경우의 수가 C[i]일 때

1) 처음에 한 칸을 올랐을 때 남은 경우의 수와
2) 처음에 세 칸을 올랐을 때 남은 경우의 수와
3) 처음에 네 칸을 올랐을 때 남은 경우의 수를 합해서 더해줘야 한다.

그렇기 때문에 4부터 n까지의 범위에서의 C[i]는 C[i-1] + C[i-3] + C[i-4]가 된다.