[백준] 9095번 (python 파이썬) 1,2,3 더하기

import sys

def solve(sumn ,n):
    if sumn > n: #더한 합이 n보다 크다면 오답
        return 0
    if sumn == n: #더한 합이 n과 같다면 정답이므로 방법1 추가
        return 1
    cnt = 0 #방법의 수를 리턴받아서 더하기때문에 초기화가 이뤄져도 괜찮다
    for i in range(1, 4): #1, 2, 3만 이용하기
        cnt += solve(sumn + i, n)
    return cnt

t = int(sys.stdin.readline()) #테스트케이스 수
for _ in range(t): 
    print(solve(0, int(sys.stdin.readline())))

중복이 가능하기 때문에 따로 예외처리를 할 필요없이 재귀로 풀면 되는 문제이다.

1부터 중복이 가능하니까 재귀를 타고 더해서 정답이면 리턴으로 1을 돌려주고 만약 n보다 크다면 0을 리턴하여 모든 방법을 찾도록 하면된다.