코드업 3704 계단 오르기

코드는 이상이 없는데 왜인지는 모르겠는데 해결이 안되네요

import sys
sys.setrecursionlimit(10000)

n = int(input())
dic={}

def step(n):
    if n in dic:
        return dic[n]
    if n <= 1:
        dic[n]=1
        return 1
    elif n == 2:
        dic[n]=2
        return 2
    else:
        dic[n] = (step(n-1)+step(n-2)+step(n-3))%1000
        return dic[n]
    
print(step(n))

분명 메모이제이션을 사용했고 출력도 문제가 없었지만

일반적인 노트북에서는 최대 재귀 횟수에 걸려서 코드가 안돌아가는 것을 보고 최대 재귀횟수를 10000건으로 늘렸는데 그냥 커널이 뻗어버리네요 다른분들을 보니 그냥 재귀 없이 반복문으로 풀었다고 합니다.

일단 문제 해설을 해보자면 저는 보면서 뭐지 순열조합인가 생각했는데, 그냥 피보나치처럼 점화식을 발견하면 되는 것이었습니다.

계단이 1개일때는 1가지 방법

계단이 2개일때는 두가지 방법 (1,1), 2

계단이 3개일 때는 4가지, 4개일때는 7가지 5개일때는 13가지 6개일때는 24가지 등등 올라가는데

이를 점화식으로 바꿔보면 n = (n-3) + (n-2) + (n-1) 이 됩니다.

종종 코테나 문제를 풀다보면 그냥 수학적인 점화식으로 해결해버리는 경우가 종종 있습니다.

그러면 뭐 끝났네요 코드는 안돌아갔지만.