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

 

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

9095번: 1, 2, 3 더하기

 

각 숫자에 대해 1, 2, 3 으로 이뤄진 경우의 수를 모두 찾는 문제였다.

만약 n > 3 이라면, 수식은 f(n) = f(n - 3) + f(n - 2) + f(n - 1) 로 세울 수 있다.

dynamic programming 을 통해 문제에서 제시한 10 이하까지 결과값을 미리 구해둔 뒤,

입력받아 출력해주었다.

 

code

 

dp = [1, 2, 4]
for i in range(3, 10):
    dp.append(dp[i - 3] + dp[i - 2] + dp[i - 1])

t = int(input())
for i in range(t):
    print(dp[int(input()) - 1])