[백준 9095 파이썬] 1, 2, 3 더하기

https://www.acmicpc.net/problem/9095

# 1, 2, 3 더하기

import sys
input = sys.stdin.readline

dp=[0] * 11
dp[1] = 1 # 1+1
dp[2] = 2 # 1+1, 2
dp[3] = 4 # 1+1+1, 1+2, 2+1, 3
dp[4] = 7 # 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1

for i in range(4, 11):
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]

T = int(input().rstrip())

for _ in range(T):
    n = int(input().rstrip())
    print(dp[n])

4를 구하는 방법 = 1의 경우의 수 + 2의 경우의 수 + 3의 경우의 수
n을 구하는 방법 = n - 1의 경우의 수 + n - 2의 경우의 수 + n - 3의 경우의 수

다른 사람 풀이 DFS

t= int(input())

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

    
for i in range(t):
    n = int(input())
    print(solution(n))

n이 작아서 dp로 푸는게 더 빠르다.