python 백준9095 1, 2, 3 더하기(BOJ9095 )

문제링크 : https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

이건 내가 알고리즘 유형에서 DP눌러서 나온 문제라서 DP로 풀었다

문제에서 점화식을 도출한다음 리스트에 초기값을 저장해둔다

그리고 반복문을 통해서 점화식을 통해 리스트 값을 불러와서 새롭게 추가하는 형태로풀었다(메모이제이션)

이렇게 하면 재귀로 호출할때와 달리 한번 계산한 값을 또 다시 계산하지 않아도 되기때문에 좋타

아직 DP문제를 많이 풀어보질못해서 메모이제이션기법 말고는 해본게 읎다..

이거 보는 사람은 아마 풀다가 막혀서 보는사람일텐데 여기까지만 읽고 다시한번 고민해보는거 추천

==================미리보기 방지====================

#테스트 케이스 수
t = int(input())

#테스트 케이스가 담길 리스트
test_case = []

#입력
for _ in range(t):
  test_case.append(int(input()))

d = [0] * 12
#초기값
d[1] = 1
d[2] = 2
d[3] = 4

#f(n) = f(n-1) + f(n-2) + f(n-3)
def test(value):
  #3보다 작으면 초기값 그대로 리터
  if value <= 3:
    return d[value]

  #그 외에는 매개변수까지만 계산후 해당 값 리턴
  for i in range(4,value+1):
    d[i] = d[i-1] + d[i-2] + d[i-3]
  return d[value]

#출력
for i in test_case:
  print(test(i))