[백준] 9095 1,2,3 더하기 - python

문제 링크

이전에 풀었던 1,2,3 더하기 4 문제가 오리지널 버전이 있다고 해서 풀어봤다.
이거는 정말 피보나치 수열 푸는 문제랑 똑같아서 이전보다 더 수월하게 풀 수 있었다.

# 1,2,3 더하기
import sys

input = sys.stdin.readline
result = []

def cal(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    else:
        return cal(n-1) + cal(n-2) + cal(n-3)

n = int(input().rstrip())
for _ in range(n):
    m = int(input().rstrip())
    print(cal(m))

n이 1, 2, 3일 때를 미리 지정해두고, 나머지는 n-1, n-2, n-3을 집어넣어서 다이나믹으로 계산하게 하였다.