Dynamic Programming
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
예제 입력
3
4
7
10
예제 출력
7
44
274
문제풀이
이 문제는 점화식을 이용해서 푸는 문제이다.
f(n) = f(n-1) + f(n-2) + f(n-3) (n>3 인 경우)
의 식이 나오게 된다!전체코드
import sys
input = sys.stdin.readline
T = int(input())
def sum(N):
if N == 1:
return 1
elif N == 2:
return 2
elif N == 3:
return 4
else:
return sum(N-1) + sum(N-2) + sum(N-3)
for i in range(T):
num = int(input())
print(sum(num))