소스코드

import sys
input = sys.stdin.readline

T = int(input().strip())

def recursive_solve(n):
	if n == 0:
		return 1
	
	if n < 0:
		return 0
		
	return recursive_solve(n-1) + recursive_solve(n-2) + recursive_solve(n-3)

for _ in range(T):
	n = int(input().strip())
	count = recursive_solve(n)
	print(count)

풀이

사실 시간복잡도로만 보면 비효율적입니다[O(3^N)]. 한 번의 호출에는 3개의 함수가 파생되기 때문입니다. 이렇게 되면 사실 동일한 값을 계산하는 함수가 중복되어 계속해서 생겨나는 비효율이 존재합니다. 이를 개선하기 위해서 DP 테이블을 만들어 다이나믹 프로그래밍을 하는 거죠.

다만 입력제한(≤ 11)이 있었기 때문에 시간 초과가 발생하지 않고 정상 실행될 수 있었습니다. 호출횟수를 계산해보자면, (3^11(약 17만) * 10 = 약 177만 번)이라고 하네요. 만약 n이 100 이상이면 시간 초과로 절대 통과할 수 없다고 합니다.