[백준] 15988번 1, 2, 3 더하기 3(python)

문제)

알고리즘)

목표금액(goal)

ex)

    goal = 2 일때  (1,1), (2)  총 2가지

    goal = 3 일때 (1,1,1), (1,2), (2,1), (3) 총 4가지

    goal = 4 일때 (1,1,1,1), (2,1,1), (1,2,1), (1,1,2), (2,2) (3,1), (1,3) 총 7가지

                                                   .

                                                   .

                                                   .

  goal= n 일때  goal[n] = goal[n-1] + goal[n-2] + goal[n-3] 형태의 점화식

코드)

# 1, 2, 3 더하기 3
import sys
input = sys.stdin.readline

goals = [1, 2, 4, 7] #1, 2, 4, 7, 13, 24, 44 ~

for _ in range(int(input())): #테스트 갯수
    n = int(input())
    for i in range(len(goals), n):
        goals.append((goals[i-3] + goals[i-2] + goals[i-1])%1000000009)  #점화식
    print(goals[n-1])