[백준 / 파이썬] 9095번 1, 2, 3 더하기

n = int(input())

def sm(num):
    if num == 1:
        return 1
    elif num == 2:
        return 2
    elif num == 3:
        return 4
    else:
        return sm(num-1) + sm(num-2) + sm(num-3)

for i in range(n):
    num = int(input())
    print(sm(num))

 

DP문제

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), (1+3), (2+1+1), (2+2), (3+1) - 7개

5 - (1+1+1+1+1), (1+1+1+2), (1+1+2+1), (1+1+3), (1+2+1+1), (2+1+1+1), (1+2+2), (2+1+2), (2+2+1), (1+3+1), (3+1+1), (2+3), (3+2) - 13개

 

4의 경우 1, 2, 3의 경우의 수를 합한 것과 같고 5의 경우 2, 3, 4의 경우의 수를 합한 것과 같다

f(n) = f(n-1)+ f(n-2)+f(n-3)