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

1 -> 1     :1개 2-> 1+1, 2 :2개 3-> (1+1+1), (1+2), (2+1), 3 : 4개 4-> (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2), (1+3), (3+1) : 7개

 

점화식으로 표현하면

f(n) = f(n-1)+ f(n-2) + f(n-3) , (n>3인 경우)

 

N = int(input())

def Add(i):
    if i == 1:
        return 1
    if i == 2:
        return 2
    if i == 3:
        return 4
    return Add(i-1)+Add(i-2)+Add(i-3)

for i in range(0,N):
    i = int(input())
    print(Add(i))