9095 1,2,3 더하기

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

#dp

9095번: 1, 2, 3 더하기

#원래 계획에는 없었는데 이 시리즈 한번 해볼려고 함 ㅇㅇ

 

#9095 1,2,3 더하기 정리

import sys

input=sys.stdin.readline

t=int(input())

order=[]

for i in range(t):

    order.append(int(input()))

dp=[i for i in range(3)]

dp[0]=1

for i in range(3,max(order)+1):
    
    dp.append(dp[i-3]+dp[i-2]+dp[i-1])

for num in order:

    print(dp[num])

 

#풀어냈다. 사실 더하기 4 에 비하면 비교적 간단한 문제였다. 하는 방법은 1 2 3 을 오른쪽 혹은 왼쪽에만 놓는다고 생 각하면 편하다 예를 들어 4면

1

11 2

111 12 21 3

에서 위에서부터 3 2 1 을 오른쪽으로 놓는다고 생각하면

13

112 22

1111 121 211 31

이렇게 모든 경우가 다 되게 된다. 

사실 점화식으로 풀었다기 보다는 이전 문제에서 생각했던것을 사용했기 때문에 문제 푼 보람은 크게 없지만 그래도 머 풀었으니깐 하하..