9095 - 1, 2, 3 더하기 (silver 3)

"""
9095 - 1, 2, 3 더하기 (silver 3)
"""
import sys

input = sys.stdin.readline

COUNT = 0


def dfs(N):
    global COUNT
    for i in range(1, 4):
        if N > i:
            dfs(N - i)
        elif N == i:
            COUNT += 1


T = int(input().rstrip())
for _ in range(T):
    N = int(input().rstrip())
    dfs(N)
    print(COUNT)
    COUNT = 0

한번에 정답! 

DFS 개념을 전 문제에서 처음 접하고 활용했는데, 이게 DFS 맞는지 잘 모르겠다~

다른 사람들은 DP문제라고 규칙성 찾아서 풀었다. 

tc = int(input())
data = [1, 2, 4]

for i in range(3, 10) :
  data.append(data[i-1] + data[i-2] + data[i-3])

for i in range(tc) :
  n = int(input())
  print(data[n-1])