Dynamic Programming(DP) - 1, 2, 3 더하기[9096]

m = int(input())
result = []
for _ in range(m):
    n = int(input())
    dp = [0, 1, 2, 4]
    
    if n >= 4:
        for i in range(4, n+1):
            nextDP = dp[i-1] + dp[i-2] + dp[i-3]
            dp.append(nextDP)
                                           
    result.append(dp[n])
        
for i in result:
    print(i)

 

Idea

규칙을 찾는 것이 Point

1, 2, 3 만으로 연산을 하여 해당 숫자를 만들 수 있는 경우의 수를 구해야했기 때문에 아래처럼 규칙이 나타났다.

 

A(n) = A(n-1) + A(n-2) + A(n-3)

A(1)	A(2)	A(3)	A(4)	A(5)	A(6)
1	1+1	1+1+1 (A(2)+ 1)	1+1+1+1 (A(3) + 1)	1+1+1+1+1 (A(4) + 1)	1+1+1+1+1+1 (A(5) + 1)
-	2	2+1 (A(2) + 1)	2+1+1 (A(3) + 1)	2+1+1+1 (A(4) + 1)	2+1+1+1+1 (A(5) + 1)
-	-	1+2 (A(1) + 2)	1+2+1 (A(3) + 1)	1+2+1+1 (A(4) + 1)	1+2+1+1+1 (A(5) + 1)
-	-	3	3+1  (A(3) + 1)	1+1+2+1  (A(4) + 1)	1+1+2+1+1 (A(5) + 1)
-	-	-	2+2 (A(2) +2)	2+2+1 (A(4) + 1)	1+1+1+2+1 (A(5) + 1)
-	-	-	1+1+2 (A(2) + 2)	3+1+1 (A(4) + 1)	3+1+1+1 (A(5) + 1)
-	-	-	1+3 (A(1) + 3)	1+3+1 (A(4) + 1)	1+3+1+1 (A(5) + 1)
-	-	-	-	3+2  (A(3) + 2)	1+1+3+1 (A(5) + 1)
-	-	-	-	1+2+2  (A(3) + 2)	2+2+1+1 (A(5) + 1)
-	-	-	-	2+1+2  (A(3) + 2)	2+1+2+1 (A(5) + 1)
-	-	-	-	1+1+1+2  (A(3) + 2)	1+2+2+1 (A(5) + 1)
-	-	-	-	2+3 (A(2) + 3)	3+2+1 (A(5) + 1)
-	-	-	-	1+1+3 (A(2) + 3)	2+3+1 (A(5) + 1)
-	-	-	-	-	3+1+2 (A(4) + 2)
-	-	-	-	-	2+2+2 (A(4) + 2)
-	-	-	-	-	1+1+2+2 (A(4) + 2)
-	-	-	-	-	1+2+1+2 (A(4) + 2)
-	-	-	-	-	2+1+1+2 (A(4) + 2)
-	-	-	-	-	1+1+1+1+2 (A(4) + 2)
-	-	-	-	-	2+1+3 (A(3) + 3)
-	-	-	-	-	1+1+1+3 (A(3) + 3)
-	-	-	-	-	2+1+3 (A(3) + 3)
-	-	-	-	-	1+2+3 (A(3) + 3)
-	-	-	-	-	3+3 (A(3) + 3)
1개	2개	4개	7개	13개	24개

1	2	3	4	5	6
A(1)	A(2)	A(3)	A(1)+A(2)+A(3)	A(2)+A(3)+A(4)	A(3)+A(4)+A(5)