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

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

---

알고리즘 분류

• 다이나믹프로그래밍

문제풀이

d[i]는 i를 만들기 위한 방법의 수

d[1]=1 -> 1
d[2]=1+1, 2 -> 2
d[3]=1+1+1, 1+2, 2+1, 3 -> 4
d[4]=1+d[3]의 원소들, 2+d[2]의 원소들, 3+d[1]의 원소들
...

소스코드

t=int(input())
for k in range(t):
  n=int(input())

  d=[0]*12
  d[1]=1
  d[2]=2
  d[3]=4

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

  print(d[n])