1,2,3 더하기 – 실버 3

N = int(input())

def sol(n):
  if n == 1:
    return 1
  elif n == 2:
    return 2
  elif n == 3:
    return 4
  else:
    return sol(n-1) + sol(n-2) + sol(n-3)

for i in range(N):
  n = int(input())
  print(sol(n))

1 = 1/

2 = 2/

3 = 4/

4 = 7/

5 = 13

 

위의 값은 경우의 수 이며 4와 5를 보면 해당 값들이 전의 값 3개의 더한 것임을 알 수 있다. 그러므로 점화식을 세워서 풀어 재귀로 풀었으나 하향식을 이용하여 배열에 값을 넣어두는 방식도 얼마든지 이용할 수 있다.

 

T = int(input())

for i in range(T) :
    n = int(input())
    dp = [0]*(n+1)
    if n == 1 :
        print(1)
    elif n == 2 :
        print(2)
    elif n == 3 :
        print(4)
    else :
        dp[1] = 1
        dp[2] = 2
        dp[3] = 4
        for j in range(4,n+1) :
            dp[j] = dp[j-1] + dp[j-2] + dp[j-3]
        print(dp[n])

n이 3보다 클 때 (n>3),f(n)=f(n-1)+f(n-2)+f(n-3)