백준 9095 1, 2, 3 더하기(python)

def ccount(n):

    dp=[0]*(n+1)

    dp[0]=1

    if n>=1:

        dp[1]=1

    if n>=2:

        dp[2]=2

    if n>=3:

        dp[3]=4

    for i in range(4, n+1):

        dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

    return dp[n]

n=int(input())

arr= [int(input()) for _ in range(n)]

for i in arr:

    print(ccount(i))

 

def ccount(n, memo):

    if n<0:

        return 0

    if n==0:

        return 1

    if n in memo:

        return memo[n]

    memo[n]=ccount(n-1, memo)+ccount(n-2, memo)+ccount(n-3, memo)

    return memo[n]

n=int(input())

arr=[int(input()) for _ in range(n)]

for i in arr:

    print(ccount(i, {}))

 

위에꺼가 약간 더 빠르다