[백준/Python] 9095. 1,2,3 더하기

 

• dfs를 이용한 중복순열로 해결하였다.

TC = int(input())

for tc in range(1,TC+1):
    N = int(input())
    cnt = 0
    
    def dfs(level):
        global cnt
        if level > N: # level의 값이 목표값을 넘어가면 리턴
            return

        if level == N: # 목표값이 되었을 때, cnt + 1
            cnt += 1
            return

        for i in range(1,4): # 1~3 까지의 수의 중복순열 구하기
            dfs(level+i)

    dfs(0)
    print(cnt)