[백준][동적 계획법1] 9507. Generations of Tribbles (파이썬/Python)

<오답>

import sys
input = sys.stdin.readline

def koong(n):
    
    if n < 2:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    elif n > 3:
        return koong(n-1)+koong(n-2)+koong(n-3)+koong(n-4)

t = int(input())

for _ in range(t):
    n=int(input())
    print(koong(n))

# 큰 수를 넣어야 하기 때문에 시간초과가 나온다. 

# 동적 계획법으로 풀어야 한다.

 

<정답>

import sys
input = sys.stdin.readline

t = int(input())
for _ in range(t):
    n = int(input())
    dp = [1,1,2,4]       
    for i in range(4,n+1):
        dp.append(dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4])
    print(dp[n])