[BAEKJOON] 1, 2, 3 더하기 - python

1, 2, 3 더하기

알고리즘 - dynamic programming

과정:

n=1 : 1 -> 1

n=2 : 1+1, 2 -> 2

n=3 : 1+1+1, 1+2, 2+1, 3 -> 4

n=4 : 1+1+1+1,1+1+2,1+2+1,1+3, 2+1+1, 2+2, 3+1 -> 7

cnt = int(input())
arr = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0] #n은 양수이며 11보다 작음
for a in range(0,cnt):
    n = int(input())
    for i in range(4,n+1):
        arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
    print(arr[n])