[ Baekjoon : python ] 백준 9095번 1, 2, 3 더하기 - 다이나믹프로그래밍

[  BAEKJOON ONLINE JUDGE  ] 9095번 1, 2, 3 더하기 _ Python 파이썬

 

" 문제 "

 

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

---

" 아이디어 "

D[n] = n을 1,2,3의 합으로 나타내는 방법의 수

 

D[n] = D[n-1] + D[n-2] + D[n-3] (n>=3)

D[n] = 1 (n=0, n=1)

D[n] = 2 (n=2)

 

---

" 코드 "

 

import sys
sys.setrecursionlimit(10000000)
 
def calc(n):
  if n==0: return 1
  if n==1: return 1
  if n==2: return 2
 
  if (m[n]==0):
    m[n] = calc(n-1) + calc(n-2) + calc(n-3)
 
  return m[n]
 
 
t = int(input())
for _ in range(t):
  n = int(input())
  m = [0]*(n+1)
  print(calc(n))
 

---

" 참고자료 "