백준 python(파이썬) 9095 1,2,3 더하기

백준 링크: https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

정말 간단한 dp문제였지만 규칙을 찾는데 시간을 너무 많이 써버렸다.

1= [1] cnt =1

2=[1.1] , [2]  cnt = 2

3=[1,1,1] , [1,2] , [2.1] , [3] cnt = 4

4=[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [3,1], [1,3] cnt =7 

3까지는 dp에 저장을 한 후 3 이후부터 dp[n-1] + dp[n-2] + dp[n-3] 을 행하면 알맞는 값이 나왔다.

 

코드:

TC=int(input())
for i in range(TC):
    dp = [0, 1, 2, 4]
    n=int(input())
    for i in range(4,n+1):
        dp.append(dp[i-3]+dp[i-2]+dp[i-1])
    print(dp[n])

풀이 자체는 쉽지만 나는 꽤 오랜 시간을 쓴것같다. dp가 너무 어렵다 ㅜㅜ