알고리즘 공부

1,2,3 더하기
https://www.acmicpc.net/problem/9095
1과 2와 3의 합으로 n을 만드는 문제
계산해보면 1은 1, 2는 2랑 1+1, 3은 3이랑 1+2랑 2+1이랑 1+1+1이렇게
[1,2,4]개 씩이고 4는 1에 3, 2에 2, 3에 1 더한게 전부이다.
따라서 그 뒤로도 쭉 전에꺼에 1, 전전에꺼에 2, 전전전에꺼에 3 더하는게 전부이고,
점화식이 dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 된다.
처음에는 생각이 아예 안났는데 역시 직접 해보니까 알 수 있었다.

def solution(N, numbers):
    for i in range(3, 11):
        numbers.append(numbers[i-1]+numbers[i-2]+numbers[i-3])
    return(numbers[N-1])
    
T= int(input())
numbers=[1,2,4]
for _ in range(T):
    print(solution(int(input()), numbers))   

소요시간 ; 30분