[알고리즘][백준] 9095번 1, 2, 3 더하기 - 파이썬(python) 풀이

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

9095번: 1, 2, 3 더하기

---

무슨 규칙이 있나 살펴보니

1 = 1
2 = 2
3 = 4
4 = 7 = 1 + 2 + 4
5 = 13 = 2 + 4 + 7

앞의 세수를 더하면 값이 나온다!

 

5의 경우

4에서 1더하기

3에서 2더하기

2에서 3더하기

3가지 종류가 있기 때문에 위와 같이 나오게 된다.

 

코드는 아래와 같다!

import sys

t = int(sys.stdin.readline())

dp = [0] * 11
dp[1] = 1
dp[2] = 2
dp[3] = 4

for _ in range(t):
    n = int(sys.stdin.readline())

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

    print(dp[n])