[파이썬] BOJ_9095(1, 2, 3 더하기)

문제

 

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

9095번: 1, 2, 3 더하기

---

 

해설

 

방법의 수를 계산해보면

1, 2, 4, 7, 13, 24가 나오는데

이걸 보면 

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]인 것을 알 수 있다.

 

 

 

처음엔 5까지만 방법의 수를 세보고 

dp[i]의 방법의 수는 그 이전 수들의 방법의 수의 총합이라고 생각했는데

6까지 세어보니 완전 아니었다..

완전 헛짓거리 하고 있었다.

---

코드

 

-파이썬

#백준 9095(1, 2, 3 더하기)

t = int(input())

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

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