[baekjoon] 백준 9095번 : 1, 2, 3 더하기 (by python 파이썬) 다이나믹 프로그래밍

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

9095번: 1, 2, 3 더하기

 

정답 code

#1, 2, 3 더하기
def sol(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 4
    
    else:
        return sol(n-1) + sol(n-2) + sol(n-3)

t = int(input())

for _ in range(t):
    n = int(input())
    print(sol(n))

 

solution

n = 1 이면 방법의수 는 1

n = 2 이면 방법의 수는 2

n = 3 이면 방법의 수는 4

 

n = 4이면 방법의 수는 7 (n=3 + n=2 + n=1) 방법의 수 7

.

.

.

이런식으로 n-1 n-2 n-3을 더한 값이 n의 방법의 수가 된다. 이를 이용해 해결하면 된다