백준 알고리즘 파이썬(Python) 9095번 1, 2, 3 더하기

---

규칙성을 찾아낸 뒤 DP를 이용하여 풀이하는 문제이다.

우선 숫자가 작은 경우 직접 개수를 세 규칙성을 찾는다.

 

1일 때 ->  1
2일 때 ->  2
3일 때 ->  4
4일 때 ->  7
5일 때 ->  13

이에 따라 점화식은   f(n) = f(n-1) + f(n-2) + f(n-3)  (n>3 인 경우)

 

n = int(input())

def sums(n):
    if n == 1:
        return(1)
    elif n == 2:
        return(2)
    elif n == 3:
        return(4)
    else:
        return sums(n-1) + sums(n-2) + sums(n-3) #규칙을 찾아내는게 중요!
        
for i in range(n):
    a = int(input())
    print(sums(a))