9095번 : 1,2,3 더하기 - Python

문제

https://www.acmicpc.net/problem/9095

풀이

정수 1일때
방법은 (1) 1개이다.

정수 2일때
방법은 (1+1), (2) 2개이다.

정수 3일때
방법은 (1+1+1), (1+2), (2+1), (3) 4개이다.

정수 4일때
방법은 (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2), (1+3), (3+1) 7개이다.

여기서 정수 4일때는 (정수1일때 + 3) + (정수2일때 + 2) + (정수3일때 +1) 인걸 알 수 있다.

점화식 : dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

코드

from sys import stdin, stdout

input = stdin.readline 

t = int(input())

array = [0 for i in range(12)]
array[1] = 1
array[2] = 2
array[3] = 4


for i in range(t) : 
    n = int(input())

    for j in range(4, n+1):
        array[j] = array[j-1] +array[j-2] +array[j-3]
        
    print(array[n])