[python][백준/BOJ] 9095번 : 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

 

✅ 문제 풀이

dp문제이므로 점화식을 찾기위해서 n=1일 때부터 가능한 방법의 수를 찾아본다. 

n=1일 때, 가능한 방법의 수는 => 1가지

n=2일 때, 1+1,2 => 2가지

n=3일 때, 1+1+1, 1+2, 2+1, 3 => 4가지

n=4일 때, => 7가지

n=5일 때, => 13가지

n=6일 때, => 24가지 ....

여기서 보다보면 n>3일 때부터, 점화식 d[n]=d[n-1]+d[n-2]+d[n-3] 인 것을 알 수 있다. 

import sys

t=int(sys.stdin.readline())

for i in range(t):
    n=int(sys.stdin.readline())
    d = [0]*(n+1)
    if n==0:
        print(0)
    elif n==1:
        print(1)
    elif n==2:
        print(2)
    elif n==3:
        print(4)
    else:
        d[1]=1
        d[2]=2
        d[3]=4

        for j in range(4,n+1):
            d[j]=d[j-1]+d[j-2]+d[j-3]
        print(d[n])