[dp/백준] 9095번: 1,2,3 더하기(2차)

-문제: https://www.acmicpc.net/problem/9095

 

점화식을 이용해서 풀어야하는 것은 알고 있었지만 1,2,3으로만 숫자 구성해야하는 거를 간과함

그래서 f(1)=1, f(2)=1, f(3)=3으로 생각해서 점화식이 이상하게 나왔음 

근데 1,2,3은 각각 1,2,3으로도 구성 가능하므로 f(1)=1, f(2)=2, f(3)=4 이다 

따라서 점화식은 f(n)=f(n-1)+f(n-2)+f(n-3)

이거를 통해서 만든 풀이는 다음과 같다 

 

-정답풀이

t=int(input())
for _ in range(t):
    dp=[0]*12
    n=int(input())
    dp[1],dp[2],dp[3]=1,2,4
    if n<=3:
        print(dp[n])
    else:
        for i in range(4,n+1):
            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
        print(dp[n])