백준 9095번 1, 2, 3 더하기 파이썬

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

9095번: 1, 2, 3 더하기

내 답안

dp = [0, 1, 2, 4, 0, 0, 0, 0, 0, 0, 0]
for i in range(int(input())):
    n = int(input())
    if n == 1 or n == 2 or n == 3:
        print(dp[n])
    else:
        for i in range(4, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
        print(dp[n])

---

처음 접근할 때는 DFS로 돌려서 풀었다.

DFS를 돌려보니 규칙이 보였고, 직접 n == 5 인 경우까지 구해봤다.
1 일때 (1) → 1개
2 일때 (1, 1) (2) → 2개
3 일때 (1, 1, 1) (1, 2) (2, 1) (3) → 4개
4 일때 (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (2, 1, 1) (2, 2) (1, 3) (3, 1) → 7개
5 일때 (1, 1, 1, 1, 1) (1, 1, 1, 2) (1, 1, 2, 1) (1, 2, 1, 1) (1, 2, 2) (1, 1, 3) (1, 3, 1) (2, 1, 1, 1) (2, 1, 2) (2, 2, 1) (2, 3) (3, 1, 1) (3, 2) → 13개
규칙 확인 까지 완료 했고
다이나믹 프로그래밍을 활용할수 있어서 DP 배열을 사용 하였다.

내가 구한 점화식은
dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3] 이다. (n > 3)
따라서 1, 2, 3 인 경우는 미리 dp 배열에 넣어두고
n 값에 따라 구해주면 된다.