[python3] 9095번 1, 2, 3 더하기

f(1)일때는 경우의 수가 1, f(2)일때는 경우의 수가 2, f(3)일때는 경우의 수가 4, f(4)일때는 경우의 수가 7이다.

이를 통해 추론해보면 f(n)을 구하기 위한 점화식이 f(n - 1) + f(n - 2) + f(n - 3) 라는 것을 확인할 수 있다.

이 점화식을 이용해서 코드를 짜보니 성공적으로 문제가 풀어졌다.

문제풀이

DP = [0] * 11
DP[0:3] = 1,2,4

T = int(input())

for RPT in range(0,T):
    n = int(input())
    for rpt in range(3,n): 
        DP[rpt] = DP[rpt - 1] + DP[rpt - 2] + DP[rpt - 3]
    print(DP[n - 1],end="\n")