[BOJ] 9095번 - 1, 2, 3 더하기

---

문제설명

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

9095번: 1, 2, 3 더하기

사고과정

• 경우의 수를 n = 5까지 나열해보고 '뒤의 입장'에서 생각해보려고 하는데 규칙을 찾지 못했다..
• 풀이를 보니 매우 간단한 규칙이였다.. n이 4이상부터는 n-1, n-2, n-3일 때의 개수를 합해주면 된다.. 이런.. 매우 간단한 걸 캐치 못하다니..😢
• 점화식으로 나타내면 다음과 같다. $dp[i] = dp[i-1] + dp[i-2] + dp[i-3]$

풀이(스스로 못 푼 풀이)

for tc in range(int(input())):
    n = int(input())
    dp = [0] * 12
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    for i in range(4, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

    print(dp[n])