백준 9095번 1,2,3 더하기 https://www.acmicpc.net/problem/9095

baekjoon9095.py

# DP는 조합관련 문제에 사용, 조합 관련 문제일 때 점화식에 더하기 사용
# 타일 조합 문제의 경우 2x1을 제외하고 나머지는 2xn조합에서(n > 1)
# 주어진 타일을 조합하며 사용하면 되므로 더하기 사용
# 이 문제의 경우.
# 1일 때 (1), 2일 때 (1, 1), (2) 와 같은 조합처럼
# n=2 일때 n-3을 할 수 없음, 즉 n >= 0


def f(n):
    if n <= 1:
        return 1
    if d[n] > 0:
        return d[n]
    if n-1 >= 0:
        d[n] += f(n-1)
    if n-2 >= 0:  #elif로 하면 안되는 이유는 모든 조합을 구하므로
        d[n] += f(n-2)
    if n-3 >= 0:
        d[n] += f(n-3)
    return d[n]


for i in range(int(input())):
    user = int(input())
    d = [0] * (user + 1)
    print(f(user))