#9095 1, 2, 3 더하기2️⃣

문제📝

결과😍

코드💻

t = int(input())

def res(a):
  if a == 1:
    return 1
  elif a == 2:
    return 2
  elif a == 3:
    return 4
  else:
    return res(a-1)+res(a-2)+res(a-3)

for i in range(t):
  a = int(input())
  print(res(a))

풀이💡

1. 테스트 케이스 t 입력
2. 재귀함수 res 생성

이 문제는 DP 문제이다
따라서 DP 접근을 위해 패턴이나 규칙을 찾기 위해 경우의 수를 구했다.
1 -> 1개
2 -> 2개
3 -> 4개
4 -> 7개
5 -> 13개

위의 규칙을 봤을 때, 5번째는 4,3,2 번째의 경우의 수를 더한 것과 같다.
=> f(n) = f(n-1) + f(n-2) + f(n-3), (n>3)

---

참고🙏

👉 [백준] 9095번: 1, 2, 3 더하기 - 파이썬